哈夫曼树在排序算法中的案例教学研究

吐尔地·托合提，崔青，刘淑娴

（新疆大学信息科学与工程学院，乌鲁木齐 830046）

0 引言

哈夫曼树（Huffman Tree），又被称为最优二叉树，是一种带权路径长度最小的二叉树，其应用也很广泛，如基于哈夫曼树的编码[1]、压缩[2-3]、加密[4-5]、数据采样[6]等。在教学中，一般我们重点讲解带权路径长度的概念、哈夫曼树的性质、哈夫曼树的构造，以及哈夫曼编码[8]。其实，哈夫曼树也可以用来对于数据元素序列进行排序。

从哈夫曼树的性质可知，权重越大的叶子结点越靠近根结点，而权重越小的叶子结点离根结点越远。因此，将待排序序列中的每一个元素看成一个叶子结点，将元素关键码看成其权重（关键码为整形情况下），构造一棵哈夫曼树，然后层序遍历并依次输出叶子结点，就能得到基本有序（降序）序列。如果，在哈夫曼树的构造、遍历和输出过程中增设一些约束，那么也完全可以做到对数据元素的降序或升序排序。

本文在数据结构教学中，针对内部排序提出一个教学案例，在排序方法中引入哈夫曼树、二叉树的遍历、栈和队列等综合内容，通过讲解一些启发思路的知识点，一方面加深了学生对于哈夫曼树的性质、构造方法、二叉树遍历算法，以及哈夫曼树、栈和队列应用的理解和掌握，另一方面引导学生要认识到解决问题有多种方案可选，鼓励学生从知识中体会和掌握算法设计的思维方式和技巧，这有助于使学生分析问题和解决问题的能力得到提升。

1 基于哈夫曼树的排序算法思路

在待排序序列中数据元素关键码为整形（int 形）情况下，我们可以将每一个数据元素看成一个叶子结点，将数据元素关键码看成其权重构造一棵哈夫曼树。设待排序数据元素关键字序列为{5，9，15，30，18，27，10，13}，在构造哈夫曼树的过程中我们给一个约束：将权重大的结点作为左孩子，将权重小的结点作为右孩子，然后按照哈夫曼树的构造方法就能生成得到如图1 所示的一棵哈夫曼树。

我们仔细观察图1 哈夫曼树中叶子结点（待排序元素结点）分布，第一层为根，从第二层开始，发现处在第i 层上元素关键字均小于第i-1 层元素关键字，而均大于第i+1 层元素关键字，最底层上的元素关键字是最小。再观察同一个层上的元素关键字大小，从左到右，关键字大小依次变小。因此，我们对此哈夫曼树进行层序遍历并输出叶子结点关键字，就能得到一个关键字有序（降序）序列{30，27，18，15，13，10，9，5}，这样就可以做到降序排序。如果，需要进行升序排序，我们可以借助一个栈来暂存层序遍历输出序列，最后依次出栈就能得到升序排序结果。

图1 由待排序元素关键字构建的哈夫曼树

2 基于哈夫曼树的排序算法实现

根据以上分析，我们可以设计一套用来排序的哈夫曼树构造算法和排序算法。为了简单讨论，以下假设关键码为整形，而且只考虑关键码，暂不考虑数据元素其他数据项。

构造哈夫曼树时，常用一个结构数组（如Huff_Nodes）来存储哈夫曼树中每一个结点的信息。我们从二叉树的性质可知，由n 个叶子结点构建的哈夫曼树中总共有2n-1 个结点，所以结构数组Huff_Nodes 大小可设置为2n-1，其元素结构可定义如图2 所示形式。

图2 结构数组元素结构形式

其中，key 域是用来保存待排序数据元素关键字（传统算法中的结点权值weight），l_child 域和r_child域是分别用来保存该结点的左孩子和右孩子结点在数组中的下标（序号），算法中我们通过下标在结点之间建立联系。parent 域保存当前结点在哈夫曼树中的双亲结点在数组中的序号，其初始值为-1。

2.1 哈夫曼树的构造算法

开始构造哈夫曼树之前，首先把n 个关键字形成的n 个叶子结点存放在结构数组Huff_Nodes 的前n 个分量中，然后根据哈夫曼树构造基本思想和本文给出的约束条件，不断将两个根结点权重最小的子树合并为一个较大的子树，并把被生成的新子树的根结点依次按顺序存放到Huff_Nodes 数组前n 个分量后面。具体实现算法描述如下：

算法初始化Huff_Nodes 数组并依次向数组填写新生成的子树信息（子树根结点关键字、根结点左右孩子在数组中的序号），同时，还不断修改与已有子树之间的关联信息。当算法结束时，用来存储图2 所示哈夫曼树的结构数组Huff_Nodes 的最终状态如图3 所示。

图3 数组Huff_Nodes的最终状态

2.2 基于哈夫曼树层序遍历的排序算法

已构建好的哈夫曼树的根结点在数组Huff_Nodes的最后一个单元中，我们从根结点出发进行层序遍历（从上到下，从左到右），并把那些叶子结点依次暂存到一个栈中，等遍历结束就出栈所有元素，此时的出栈序列就是一个升序排序序列。如果要进行降序排序，那就不需要经过栈来改变次序，在遍历中直接输出叶子结点即可。升序排序具体实现算法描述如下：

3 结语

排序是数据结构课程最后一章内容，一般我们主要讲解各种典型内部排序算法思路，分析其性能和优缺点，然后要求学生通过运行、调试排序程序去掌握多种排序算法，但很少有拓展内容。本文针对内部排序设计一个教学案例，将栈、队列、哈夫曼树等重要内容综合应用到排序方法中。其目的不仅仅是提出一个排序算法，而更重要的是鼓励学生敢于创新，引导学生从知识中体会和掌握算法设计的思维方式和技巧，从而培养学生创造性思维能力及解决实际问题的能力。