第6章 树和二叉树 树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构上的操作及应用等。

6.1 树的基本概念 6.1.1 树的定义和基本术语 1 树的定义 树(Tree)是n(n≥0)个结点的有限集合T，若n=0时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1, T2, T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。 这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成，如图6-1(a)所示。

2 树的基本术语 ⑴ 结点(node)：一个数据元素及其若干指向其子树的分支。 ⑵ 结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。 图6-1 树的示例形式 A B D C E G F H I M J N K L (a) 只有根结点 (b) 一般的树

一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。 如图6-1(b)中结点A的度是3 ，结点B的度是2 ，结点M的度是0，树的度是3 。 ⑶ 叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。 如图6-1(b)中结点H、I、J、K、L、M、N是叶子结点，而所有其它结点都是分支结点。 ⑷ 孩子结点、双亲结点、兄弟结点 一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。

⑸ 层次、堂兄弟结点 同一双亲结点的所有子结点互称为兄弟结点。 如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、F是兄弟结点。 如图6-1(b)中结点B 、C、D是结点A的子结点，而结点A是结点B 、C、D的父结点；类似地结点E 、F是结点B的子结点，结点B是结点E 、F的父结点。 同一双亲结点的所有子结点互称为兄弟结点。 如图6-1(b)中结点B 、C、D是兄弟结点；结点E 、F是兄弟结点。 ⑸ 层次、堂兄弟结点 规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。 若某结点在第l(l≥1)层，则其子结点在第l+1层。 双亲结点在同一层上的所有结点互称为堂兄弟结点。如图6-1(b)中结点E、F、G、H、I、J。

从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。 ⑹ 结点的层次路径、祖先、子孙 从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。 结点p的层次路径上的所有结点（p除外）称为p的祖先(ancester) 。 以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent)。 ⑺ 树的深度(depth)：树中结点的最大层次值，又称为树的高度，如图6-1(b)中树的高度为4。 ⑻ 有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。

3 树的表示形式 ⑼ 森林(forest)：是m(m≥0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。 3 树的表示形式 ⑴ 倒悬树。是最常用的表示形式，如图6-1(b)。 ⑵ 嵌套集合。是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。图6-2(a)是图6-1(b)树的嵌套集合形式。 ⑶ 广义表形式。图6-2(b)是树的广义表形式。 ⑷ 凹入法表示形式。见P120 树的表示方法的多样化说明了树结构的重要性。

(A(B(E(K,L),F),C(G(M,N)),D(H,I,J) H I J D 图6-2 树的表示形式 (a) 嵌套集合形式 (b) 广义表形式 (A(B(E(K,L),F),C(G(M,N)),D(H,I,J) H I J D F B K L E C M N G A

6.1.2 树的抽象数据类型定义 ADT Tree{ 数据对象D：D是具有相同数据类型的数据元素的集合。 6.1.2 树的抽象数据类型定义 ADT Tree{ 数据对象D：D是具有相同数据类型的数据元素的集合。 数据关系R：若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 基本操作：见课本…… } ADT Tree 详见p118~119。

6.2 二叉树 6.2.1 二叉树的定义 1 二叉树的定义 二叉树(Binary tree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n>1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。 由此可知，二叉树的定义是递归的。

二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关树的术语也都适用于二叉树。 2 二叉树的基本形态 二叉树有5种基本形态，如图6-3所示。 A (a) (b) (c) (d) (e) (a) 空二叉树 (b) 单结点二叉树 (c) 右子树为空 (d) 左子树为空 (e) 左、右子树都不空 图6-3 二叉树的基本形态

6.2.2 二叉树的性质 性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≥1)。 证明：用数学归纳法证明。 6.2.2 二叉树的性质 性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≥1)。 证明：用数学归纳法证明。 当i=1时：只有一个根结点，21-1=20 =1，命题成立。 现假设对i>1时，处在第i-1层上至多有2(i-1)-1个结点。 由归纳假设知，第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。 即 2×2i-2＝2i-1性质2：深度为k的二叉树至多有2k-1个结点（k≥1) 。

证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。 由性质1知，二叉树的第1层、第2层⋯第k层上的结点数至多有： 20、21 …2k-1 。 ∴ 总的结点数至多有： 20+21+ …+2k-1=2k-1 性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，则有：N=n0+n1+n2 再看二叉树中的分支数：

除根结点外，其余每个结点都有唯一的一个进入分支，而所有这些分支都是由度为1和2的结点射出的。设B为二叉树中的分支总数，则有： N=B+1 ∴ B＝n1+2n2 ∴ N=B+1=n1+2n2+1 ∴ n0+n1+n2=n1+2n2+1 即 n0=n2+1 证毕

满二叉树和完全二叉树 一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。

8 9 4 10 11 5 12 13 6 14 15 7 2 1 3 (a) 满二叉树 (b) 完全二叉树 (c) 非完全二叉树 图6-4 特殊形态的二叉树

满二叉树的特点： ◆ 基本特点是每一层上的结点数总是最大结点数。 ◆ 满二叉树的所有的支结点都有左、右子树。 ◆ 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。 完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。 或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。 其中 2k-1 ≤ n≤2k-1 。

性质4：n个结点的完全二叉树深度为：㏒2n +1。 其中符号： x表示不大于x的最大整数。 完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。 完全二叉树的特点： 若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。 性质4：n个结点的完全二叉树深度为：㏒2n +1。 其中符号： x表示不大于x的最大整数。 x 表示不小于x的最小整数。 证明：假设完全二叉树的深度为k，则根据性质2及完全二叉树的定义有：

2k-1-1<n≤2k-1 或 2 k-1≤n<2k 性质5：若对一棵有n个结点的完全二叉树(深度为└㏒2n┘+1)的结点按层（从第1层到第㏒2n +1层)序自左至右进行编号,则对于编号为i（1≤i≤n)的结点： ⑴ 若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是 i/2 。 ⑵ 如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。 ⑶ 如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。

证明：用数学归纳法证明。首先证明⑵和⑶，然后由⑵和⑶导出⑴。 当i=1时，由完全二叉树的定义知，结点i的左孩子的编号是2，右孩子的编号是3。 若2>n，则二叉树中不存在编号为2的结点，说明结点i的左孩子不存在。 若3>n，则二叉树中不存在编号为3的结点，说明结点i的右孩子不存在。 现假设对于编号为j(1≤j≤i)的结点，(2)和(3)成立。即： ◆ 当2j≤n ：结点j的左孩子编号是2j；当2j>n时，结点j的左孩子结点不存在。

◆ 当2j+1≤n ：结点j的右孩子编号是2j+1；当2j+1>n时，结点j的右孩子结点不存在。 当i=j+1时，由完全二叉树的定义知，若结点i的左孩子结点存在，则其左孩子结点的编号一定等于编号为j的右孩子的编号加1，即结点i的左孩子的编号为： (2j+1)+1=2(j+1)=2i 如图6-5所示，且有2i≤n。相反，若2i>n，则左孩子结点不存在。同样地，若结点i的右孩子结点存在，则其右孩子的编号为：2i+1，且有2i+1≤n。相反，若2i+1>n，则左孩子结点不存在。结论(2)和(3)得证。 再由(2)和(3)来证明(1) 。 当i=1时，显然编号为1的是根结点，无双亲结点。

当i>1时，设编号为i的结点的双亲结点的编号为m，若编号为i的结点是其双亲结点的左孩子，则由(2)有： (a) i和i+1结点在同一层 … (b) i和i+1结点不在同一层 图6-5 完全二叉树中结点i和i+1的左右孩子 当i>1时，设编号为i的结点的双亲结点的编号为m，若编号为i的结点是其双亲结点的左孩子，则由(2)有： i=2m ，即m=i/2 ； 若编号为i的结点是其双亲结点的右孩子，则由(3)有： i=2m+1 ，即m=(i-1) /2 ； ∴ 当i>1时，其双亲结点的编号为i/2 。 证毕

6.2.3 二叉树的存储结构 1 顺序存储结构 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。 6.2.3 二叉树的存储结构 1 顺序存储结构 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。 对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图6-6(c)所示。 对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如图6-6(d)所示。

a b c d h i e j k l f g (a) 完全二叉树 (b) 非完全二叉树 Ø 1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l (c) 完全二叉树的顺序存储形式 1 2 3 4 5 6 7 8 9 10 11 a b c d e Ø h Ø Ø f g (d) 非完全二叉树的顺序存储形式 图6-6 二叉树及其顺序存储形式

最坏的情况下，一个深度为k且只有k个结点的单支树需要长度为2k-1的一维数组。

2 链式存储结构 (1) 结点的类型及其定义 ① 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。 2 链式存储结构 设计不同的结点结构可构成不同的链式存储结构。 (1) 结点的类型及其定义 ① 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。 typedef struct BTNode { ElemType data ; struct BTNode *Lchild , *Rchild ; }BTNode ;

② 三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图6-7(b)所示。 typedef struct BTNode_3 { ElemType data ; struct BTNode_3 *Lchild , *Rchild , *parent ; }BTNode_3 ; Lchild data Rchild Lchild data parent Rchild (a) 二叉链表结点 (b) 三叉链表结点 图6-7 链表结点结构形式

(2) 二叉树的链式存储形式 例有一棵一般的二叉树，如图6-8(a)所示。以二叉链表和三叉链表方式存储的结构图分别如图6-8(b) 、 6-8(c)所示。 图6-8 二叉树及其链式存储结构 (a) 二叉树 a f e d c b g (c) 三叉链表 a ⋀ ⋀ ⋀ c ⋀ ⋀ e ⋀ f ⋀ ⋀ g ⋀ T (b) 二叉链表 a ⋀ ⋀ c ⋀ ⋀ e ⋀ g ⋀ ⋀ f ⋀

6.3 遍历二叉树及其应用 遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。 二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 二叉树的基本组成：根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。

若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有前三种情况三种情况，分别是： 对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用堆栈来实现的。

6.3.1 先序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 访问根结点； 6.3.1 先序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 访问根结点； ⑵ 先序遍历左子树(递归调用本算法)； ⑶ 先序遍历右子树(递归调用本算法)。

说明：visit()函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量T来指向。 先序遍历的递归算法 void PreorderTraverse(BTNode *T) { if (T!=NULL) { visit(T->data) ; /* 访问根结点 */ PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } 说明：visit()函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量T来指向。

2 非递归算法 算法实现： 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； 2 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 访问p所指向的结点； ⑵ q=p->Rchild ，若q不为空，则q进栈； ⑶ p=p->Lchild ，若p不为空，转(1)，否则转(4)； ⑷ 退栈到p ，转(1)，直到栈空为止。 算法实现：

#define MAX_NODE 50 void PreorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ; if (p==NULL) { p=stack[top] ; top-- ; } } while (p!=NULL) ;

6.3.2 中序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 中序遍历左子树(递归调用本算法)； 6.3.2 中序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 中序遍历左子树(递归调用本算法)； ⑵ 访问根结点； ⑶ 中序遍历右子树(递归调用本算法)。

中序遍历的递归算法 void InorderTraverse(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(T->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } /*图6-8(a) 的二叉树，输出的次序是： cbegdfa */

2 非递归算法 算法实现： 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T 2 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T ⑴ 若p不为空，p进栈， p=p->Lchild ； ⑵ 否则(即p为空)，退栈到p，访问p所指向的结点； ⑶ p=p->Rchild ，转(1)； 直到栈空为止。 算法实现：

#define MAX_NODE 50 void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { while (p!=NULL) { stack[++top]=p ; p=p->Lchild ; } if (top==0) bool=0 ; else { p=stack[top] ; top-- ; visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } }

6.3.3 后序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 后序遍历左子树(递归调用本算法)； 6.3.3 后序遍历二叉树 1 递归算法 算法的递归定义是： 若二叉树为空，则遍历结束；否则 ⑴ 后序遍历左子树(递归调用本算法)； ⑵ 后序遍历右子树(递归调用本算法) ； ⑶ 访问根结点 。

后序遍历的递归算法 void PostorderTraverse(BTNode *T) { if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(T->data) ; /* 访问根结点 */ } } /*图6-8(a) 的二叉树，输出的次序是： cgefdba */ 遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O(n) 。

图6-9 表达式 (a+b*(c-d)-e/f)二叉树 按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是： 其先序序列为： -+a*b-cd/ef 其中序序列为： a+b*c-d-e/f 其后序序列为： abcd-*+ef/- － / f e - d c b * a + 图6-9 表达式 (a+b*(c-d)-e/f)二叉树

2 非递归算法 在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。 因此，设立一个状态标志变量tag ： 0 ： 结点暂不能访问 1 ： 结点可以被访问 tag=

其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。 若二叉树为空，则返回；否则，令p=T； ⑴ 第一次经过根结点p，不访问： p进栈S1 ， tag 赋值0，进栈S2，p=p->Lchild 。 ⑵ 若p不为空，转(1)，否则，取状态标志值tag ： ⑶ 若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元素的右子树，即p=S1[top]->Rchild ，转(1)； ⑷ 若tag=1：S1退栈，访问该结点； 直到栈空为止。

算法实现： #define MAX_NODE 50 void PostorderTraverse( BTNode *T) { BTNode *S1[MAX_NODE] ,*p=T ; int S2[MAX_NODE] , top=0 , bool=1 ; if (T==NULL) printf(“Binary Tree is Empty!\n”) ; else { do { while (p!=NULL) { S1[++top]=p ; S2[top]=0 ; p=p->Lchild ; } if (top==0) bool=0 ;

else if (S2[top]==0) { p=S1[top]->Rchild ; S2[top]=1 ; } else { p=S1[top] ; top-- ; visit( p->data ) ; p=NULL ; /* 使循环继续进行而不至于死循环 */ } } while (bool!=0) ; }

6.6 赫夫曼树及其应用 赫夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。

6.6.1 最优二叉树(Huffman树) 1 基本概念 ① 结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。 ② 路径长度：结点路径上的分支数目称为路径长度。 ③ 树的路径长度：从树根到每一个结点的路径长度之和。 例图6-23的树。A到F ：结点路径 AEF ；路径长度(即边的数目) 2 ；树的路径长度：31+52+23=19

④ 结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。 权(值)：各种开销、代价、频度等的抽象称呼。 ⑤ 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做： WPL=w1l1+w2l2+⋯+wnln=∑wili (i=1,2,⋯,n) 其中：n为叶子结点的个数；wi为第i个结点的权值； li为第i个结点的路径长度。 ⑥ Huffman树：具有n个叶子结点(每个结点的权值为wi) 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树) 。

在许多判定问题时，利用Huffman树可以得到最佳判断算法。 如图6-24是权值分别为2、3、6、7，具有4个叶子结点的二叉树，它们的带权路径长度分别为： (a) WPL=22+32+62+72=36 ； (b) WPL=21+32+63+73=47 ； (c) WPL=71+62+23+33=34 。 其中(c)的 WPL值最小，可以证明是Huffman树。

2 3 6 7 (a) (b) (c) 图6-24 具有相同叶子结点，不同带权路径长度的二叉树 2 Huffman树的构造 ① 根据n个权值{w1, w2, ⋯,wn}，构造成n棵二叉树的集合F={T1, T2, ⋯,Tn}，其中每棵二叉树只有一个权值为wi的根结点，没有左、右子树；

② 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和； ③ 在F中删除这两棵树，同时将新得到的树加入F中； ④ 重复②、③，直到F只含一颗树为止。 构造Huffman树时，为了规范，规定F={T1,T2, ⋯,Tn}中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。

图6-25是权值集合W={8, 3, 4, 6, 5, 5}构造Huffman树的过程。所构造的Huffman树的WPL是： 第一步 第二步 7 第三步 10 第四步 13 第六步 1 18 31 图6-25 Huffman树的构造过程 第五步

6.6.2 赫夫曼编码及其算法 1 Huffman编码 在电报收发等数据通讯中，常需要将传送的文字转换成由二进制字符0、1组成的字符串来传输。为了使收发的速度提高，就要求电文编码要尽可能地短。此外，要设计长短不等的编码，还必须保证任意字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 Huffman树可以用来构造编码长度不等且译码不产生二义性的编码。 设电文中的字符集C={c1,c2, ⋯,ci, ⋯,cn}，各个字符出现的次数或频度集W={w1,w2, ⋯,wi, ⋯,wn}。

Huffman编码方法 以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造 Huffman树。规定Huffman树中左分支代表“0”，右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为Huffman编码。 由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的Huffman编码不可能是另一个字符的Huffman编码的前缀。

2 Huffman编码算法实现 (1) 数据结构设计 原因： 若字符集C={a, b, c, d, e, f}所对应的权值集合为W={8, 3, 4, 6, 5, 5}，如图6-25所示，则字符a,b, c,d, e,f所对应的Huffman编码分别是：10，010，011，00 ，110，111。 2 Huffman编码算法实现 (1) 数据结构设计 Huffman树中没有度为1的结点棵有n个叶子结点的Huffman树共有2n-1个结点，则可存储在大小为2n-1的一维数组中。实现编码的结点结构如图6-26所示。 原因： ◆ 求编码需从叶子结点出发走一条从叶子到根的路径；

结点类型定义： ◆ 译码需从根结点出发走一条到叶子结点的路径。 Weight Parent Lchild Rchild Weight：权值域； Parent：双亲结点下标 Lchild, Rchild：分别标识左、右子树的下标 图6-26 Huffman编码的结点结构 ◆ 译码需从根结点出发走一条到叶子结点的路径。 结点类型定义： #define MAX_NODE 200 /* Max_Node>2n-1 */ typedef struct { unsigned int Weight ; /* 权值域 */ unsinged int Parent , Lchild , Rchild ; } HTNode ;

(2) Huffman树的生成 算法实现 void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m) /* 创建一棵叶子结点数为n的Huffman树 */ { unsigned int w ; int k , j ; for (k=1 ; k<m ; k++) { if (k<=n) { printf(“\n Please Input Weight : w=?”); scanf(“%d”, &w) ;HT[k].weight=w ; } /* 输入时，所有叶子结点都有权值 */ else HT[k].weight=0; /* 非叶子结点没有权值 */

HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ; for (k=n+1; k<m ; k++) { unsigned w1=32767 , w2=w1 ; /* w1 , w2分别保存权值最小的两个权值 */ int p1=0 , p2=0 ; /* p1 , p2保存两个最小权值的下标 */ for (j=1 ; j<=k-1 ; j++) { if (HT[k].Parent==0) /* 尚未合并 */ { if (HT[j].Weight<w1) { w2=w1 ; p2=p1 ; w1=HT[j].Weight ; p1=j ; }

说明：生成Huffman树后，树的根结点的下标是2n-1 ，即m-1 。 else if (HT[j].Weight<w2) { w2=HT[j].Weight ; p2=j ; } } /* 找到权值最小的两个值及其下标 */ } HT[k].Lchild=p1 ; HT[k].Rchild=p2 ; HT[k].weight=w1+w2 ; HT[p1].Parent=k ; HT[p2].Parent=k ; 说明：生成Huffman树后，树的根结点的下标是2n-1 ，即m-1 。

(3) Huffman编码算法 根据出现频度(权值)Weight，对叶子结点的Huffman编码有两种方式： 由Huffman树的生成知，n个叶子结点的树共有2n-1个结点，叶子结点存储在数组HT中的下标值为1∽n。 ① 编码是叶子结点的编码，只需对数组HT[1…n]的n个权值进行编码； ② 每个字符的编码不同，但编码的最大长度是n。

算法实现 求编码时先设一个通用的指向字符的指针变量，求得编码后再复制。 void Huff_coding(unsigned n , Hnode HT[] , unsigned m) /* m应为n+1,编码的最大长度n加1 */ { int k , sp ,fp ; char *cd , *HC[m] ; cd=(char *)malloc(m*sizeof(char)) ; /* 动态分配求编码的工作空间 */ cd[n]=‘\0’ /* 编码的结束标志 */ for (k=1 ; k<n+1 ; k++) /* 逐个求字符的编码 */ { sp=n ; p=k ; fp=HT[k].parent ;

for ( ; fp!=0 ;p=fp , fp=HT[p].parent) /* 从叶子结点到根逆向求编码 */ /* 从叶子结点到根逆向求编码 */ if (HT[fp].parent==p) cd[--sp]=‘0’ ; else cd[--sp]=‘1’ ; HC[k]=(char *)malloc((n-sp)*sizeof(char)) ; /* 为第k个字符分配保存编码的空间 */ trcpy(HC[k] , &cd[sp]) ; } free(cd) ;

习 题 六 ⑴ 假设在树中， 结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟? ② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?

⑵ 一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ① 各层的结点数是多少? ② 编号为i的结点的双亲结点(若存在)的编号是多少? ③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少? ④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?

① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 ⑶ 设有如图6-27所示的二叉树。 ① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 ⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。 图6-27 二叉树 a d e b f g c h k m n ⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。

⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 ⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 ⑻ 设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 ⑼ 设有一棵树，如图6-28所示。 ① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树。

⑽ 设给定权值集合w={3,5,7,8,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。 ⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码。 a d e b f g m h k c n 图6-28 一般的树