第8章 树和二叉树 树 二叉树 二叉树设计 二叉树遍历 线索二叉树 哈夫曼树 等价问题 树与二叉树的转换 树的遍历 主要知识点

8.1 树 1.树的定义 树是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。 注：树的定义具有递归性，即“树中还有树”。

若干术语 结点：由数据元素和构造数据元素之 间关系的指针组成 结点的度：结点所拥有的子树的个数 叶结点：度为0的结点，也称作 终端结点 A B C G E I D H F J L K 分支结点：度不为0的结点

孩子结点：树中一个结点的子树的根结点 双亲结点：若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点 兄弟结点：具有相同的双亲结点的结点 树的度：树中所有结点的度的最大值 结点的层次：从根结点到树中某结点所经路径上的分支数 树的深度：树中所有结点的层次的最大值

2.树的表示方法 无序树：树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树 有序树：树中任意一个结点的各孩子结点有严格排列 次序的树 森林：m（m≥0）棵树的集合 2.树的表示方法 (1)直观表示法 (2)形式化表示法 (3)凹入表示法

DF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj=￠） R={<Root, ri>, i=1,2,…,n-1} T=（D，R） DF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj=￠） R={<Root, ri>, i=1,2,…,n-1} A B E J F C G K L D H I

3.树的抽象数据类型 数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: 数据集合: 树的结点集合，每个结点由数据元素和构造数　　　　　 据元素之间关系的指针组成。 操作集合: （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）双亲结点Parent(T, curr) （4）左孩子结点LeftChild(T, curr) （5）右兄弟结点RightSibling(T, curr) （6）遍历树Traverse(T, Visit())

4.树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。 指针有常规指针和仿真指针

(1)双亲表示法 (a)一棵树 （b)仿真指针的双亲表示法存储结构 树及其使用仿真指针的双亲表示法 4 H 2 G 1 F E D C B C B -1 A I data parent 3 5 6 7 8 (1)双亲表示法 A B D E F H I C G (a)一棵树 （b)仿真指针的双亲表示法存储结构 树及其使用仿真指针的双亲表示法

常规指针的孩子表示法 root B A ∧ C D E F G H I (2)孩子表示法

(3)双亲孩子表示法 双亲孩子表示法存储结构 4 H 2 G 1 F E D C B -1 A I data parent head 3 5 ∧ 4 H 2 G 1 F E D C B -1 A I data parent head 3 5 6 7 8 child next 双亲孩子表示法存储结构

(4)孩子兄弟表示法 root ∧ B C D E F G H I A 常规指针的孩子兄弟表示法

8.2 二叉树 1.二叉树的定义 一、二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。所以下面是两棵不同的树

二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 B A C E D F G B A C E D F G 二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示

问题:一个高度为h的完全二叉树最多有多少个结点?最少有多少个结点? B A C E D F G H I J K L M N O B A C E D F G H I J (b)完全二叉树 (a)满二叉树 问题:一个高度为h的完全二叉树最多有多少个结点?最少有多少个结点?

2.二叉树抽象数据类型 数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit())

3.二叉树的性质 性质1 在一棵非空二叉树的第i层上至多有2i个结点（i≥0）。 性质2 深度为k的二叉树至多有2k+1-1个结点。

性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有 n0= n2+1。 证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点个数，则有： n = n0 + n1 + n2 另外，在二叉树中，除根结点外的所有结点都有一个惟一的进入分支，设M为二叉树中所有结点的进入分支数，则有： M = n - 1 从二叉树的结构可知，二叉树的所有进入分支是由度为1的结点和度为2的结点发出的，每个度为1的结点发出一个分支，每个度为2的结点发出两个分支，所以又有： M = n1 + 2 × n2 因此有： n - 1 = n1 + 2 × n2 再把 n=n0+n1+n2 代入，则可以得到 n0 = n2 + 1。

性质4 具有n个结点的完全二叉树的深度k为大于或等于lb(n+1)-1的最小整数。 证明：由性质2和完全二叉树的定义可知，对于有n个结点的深度为k的完全二叉树有：2k-1 < n ≤ 2k+1-1 移项有：2k < n+1 ≤ 2k+1 对不等式求对数，有：k < lb(n+1) ≤ k+1 因为lb(n+1)介于k和k+1之间且大于k，而二叉树的深度又只能是整数，所以必有k为大于或等于lb(n+1)-1的最小整数。 可简写为k=lb(n+1)-1。例如，2.0=2，2.1=3。 若结点个数n=0，则有深度k=-1，满足k=lb(0+1)-1=-1； 若结点个数n=1，则有深度k=0，满足k=lb(1+1)-1=0； 若结点个数n=2，则有深度k=1，满足k=lb(2+1)-1 =0.xx =1； 若结点个数n=3，则有深度k=1，满足k=lb(3+1)-1=1。

性质5 对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0≤i < n),有： (1)如果i>0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0，则结点i是根结点，无双亲。 (2)如果2i+1＜n ，其左孩子是结点2i+1；如果2i+1≥n，则结点i无左孩子。 (3)如果2i＋2＜n，其右孩子是结点2i＋2；如果2i＋2≥n，则结点i无右孩子。

8.3二叉树的设计和实现 8.3.1二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。 1. 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：

B A C E D F G H I J K L M N O A B C D O N M L K J I H G F E 1 2 4 3 5 7 6 11 8 10 9 12 13 14

B A C E D F G H I J A B C D J I H G F E 1 2 4 3 5 7 6 8 9 对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。

(b)完全二叉树形态 (a)一般二叉树 (c) 在数组中的存储形式 A B C ∧ G F E D 1 2 4 3 5 7 6 11 8 4 3 5 7 6 11 8 10 9 12 数组 下标 (c) 在数组中的存储形式

2. 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为： rightChild data leftChild 二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链存储结构的二叉树见下图(b)，不带头结点的二叉链存储结构的二叉树如下图(a)所示。

(b)带头结点的二叉树 (a)不带头结点的二叉树 图8-10 二叉链存储结构的二叉树 root root ∧ A B C D E F G A

3.二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。 二叉树的仿真二叉链存储结构

8.3.2二叉链结构的二叉树设计 /*初始化*/ typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode; /*初始化*/ void Initiate(BiTreeNode **root) { *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; }

/*左子树插入结点*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t;   if(curr == NULL) return NULL; t = curr->leftChild; s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t; s->rightChild = NULL;   curr->leftChild = s; return curr->leftChild; }

/*删除左子树*/ BiTreeNode *DeleteLeftTree(BiTreeNode *curr) { if(curr == NULL || curr->leftChild == NULL) return NULL;   Destroy(&curr->leftChild); curr->leftChild = NULL; return curr; }

例8-1 编写一个建立如图8-10（b）所示的带头结点的二叉链存储结构二叉树的程序。 #include <stdlib.h> #include <stdio.h> typedef char DataType; #include "Bitree.h“ Void main(void) { BiTreeNode *root, *p, *pp;   Initiate(&root); p = InsertLeftNode(root, 'A'); p = InsertLeftNode(p, 'B'); p = InsertLeftNode(p, 'D'); p = InsertRightNode(p, 'G'); p = InsertRightNode(root->leftChild, 'C'); InsertLeftNode(p, 'E'); InsertRightNode(pp, 'F'); }

8.4 二叉树遍历 8.4.1 二叉树遍历 1.二叉树遍历的基本方法 从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，根据遍历算法对访问根结点处理的位置，称下面三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。

前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 对于图8-7（b）所示的二叉树，前序遍历访问结点的次序为： A B D G C E F

中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 对于图8-7（b）所示的二叉树，中序遍历访问结点的次序为： D G B A E C F

后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 对于图8-7（b）所示的二叉树，后序遍历访问结点的次序为： G D B E F C A

此外，二叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。 它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。

二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得一个结点指针，访问该结点； （3.b）若该结点的左子树非空，则将该结点的左子树指 针入队列； （3.c）若该结点的右子树非空，则将该结点的右子树指 针入队列； （4）结束。

当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的。 2.二叉树的遍历方法和二叉树的结构 二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，一个二叉树的遍历序列不能决定一棵二叉树，但某些不同的遍历序列组合可以惟一确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树的结构。

为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。 8.4.2 二叉链存储结构下二叉树遍历的实现 void PreOrder(BiTreeNode *t, void Visit(DataType item)) /*前序遍历二叉树t，访问操作为Visit()函数*/  { if(t != NULL) { Visit(t->data); PreOrder(t->leftChild, Visit); PreOrder(t->rightChild, Visit); } 为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。

void InOrder(BiTreeNode *t, void Visit(DataType item)) /*中序t */ { if(t != NULL) { InOrder(t->leftChild, Visit); Visit(t->data); InOrder(t->rightChild, Visit); }   void PostOrder(BiTreeNode *t, void Visit(DataType item)) /*后序 */ { PostOrder(t->leftChild, Visit); PostOrder(t->rightChild, Visit);

二叉树撤消操作函数 二叉树的撤消操作实际上是二叉树遍历操作的一个具体应用。由于二叉树中每个结点允许有左孩子结点和右孩子结点，所以在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作算法实现如下：

void Destroy(BiTreeNode **root) { if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild);   if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); }

8.4.3 二叉树遍历的应用 1 打印二叉树 把二叉树逆时针旋转900C，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转900C后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。

void PrintBiTree(BiTreeNode *bt, int n) { int i; if(bt == NULL) return; PrintBiTree(bt->rightChild, n+1); for(i = 0; i < n-1; i++) printf(" "); if(n > 0) printf("---"); printf("%c\n", bt->data); } PrintBiTree(bt->leftChild, n+1);

2 查找数据元素 在二叉树中查找数据元素操作的要求是：在bt为根结点指针的二叉树中查找数据元素x，若查找到数据元素x时返回该结点的指针；若查找不到数据元素x时返回空指针。 在二叉树bt中查找数据元素x算法可设计成先序遍历算法，此时查找结点的次序是：首先在根结点查找，然后在左子树查找，最后在右子树查找。但是，和常规递归算法不同的是，此算法当一个分支上的结点比较完仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，此算法是一个回溯算法 。

BiTreeNode *Search(BiTreeNode *bt, DataType x) { BiTreeNode *p; if(bt == NULL) return NULL; if(bt->data == x) return bt; if(bt->leftChild != NULL) { p = Search(bt->leftChild, x); if(p != NULL) return p; } if(bt->rightChild != NULL) { p = Search(bt->rightChild, x); if(p != NULL) return p;   return NULL;

3.应用举例 例8-2 编写一个程序，首先建立如图8-10（b）所示的带头结点的二叉链存储结构二叉树，然后打印该二叉树，最后输出分别按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序访问各结点的序列信息。 设计： 输出显示函数设计：按照某种遍历方法输出显示二叉树各结点的信息，其实就是把上述各遍历二叉树函数中的Visit()函数设计成输出显示结点信息的函数。Visit()函数设计如下： void Visit(DataType item) { printf("%c ", item); }

8.4.4.非递归的二叉树遍历算法 所有递归算法都可以借助堆栈转换成循环结构的非递归算法，通常有两种方法：一种方法是形式化模拟转换，另一种方法是根据要求解问题的特点设计借助堆栈的循环结构算法。 非递归的二叉树前序遍历算法如下： （1）初始化设置一个堆栈； （2）把根结点指针入栈； （3）当堆栈非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出栈取得一个结点指针，访问该结点； （3.b）若该结点的右子树非空，则将该结点的右子树指 针入栈； （3.c）若该结点的左子树非空，则将该结点的左子树指 针入栈； （4）结束。

问题： （1）这个算法和哪个算法相似？ （2）为什么相似？ （3）非递归的二叉树前序遍历算法有什么用途？

8.5 线索二叉树 线索二叉树是另一种分步遍历二叉树的方法。它既可以从前向后分步遍历二叉树，又可以从后向前分步遍历二叉树。 当按某种规则遍历二叉树时，保存遍历时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。 对二叉链存储结构的二叉树分析可知，在有n个结点的二叉树中必定存在n+1个空链域。

规定：当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因此我们再在结点中增加两个线索标志位来区分这两种情况。

线索标志位定义如下： 每个结点的结构就如下所示： leftThread leftChild data rightChild rightThread 结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。

A D G E C F (a) B 1 (b) (d) (c) root 线索二叉树

一旦建立了某种方式的线索二叉树后，用户程序就可以像操作双向链表一样操作该线索二叉树。 例如，一旦建立了中序线索二叉树后，用户程序就可以设计一个正向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的第一个结点位置，每次循环使指针指向当前结点的中序遍历的后继结点位置，当指针指向中序线索二叉树的最后一个结点位置后循环过程结束；或者用户程序可以设计一个反向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的最后一个结点位置，每次循环使指针指向当前结点的中序遍历的前驱结点位置，当指针指向中序线索二叉树的第一个结点位置前循环过程结束。

这种算法设计要求分别设计三个函数： First()：定位在第一个结点位置； Next()：移动到下一个结点位置； End()：是否已经到最后下一个结点位置； 当然，还需要一个根据二叉树构造线索二叉树的函数。

typedef struct { ThreadBiNode *root; ThreadBiNode *current; int nextComplete; }ThreadBiTree; void ThreadInitiate(ThreadBiTree *tree, ThreadBiNode *root) { tree->root = root; tree->current = root; if(root == NULL) tree->nextComplete = 1; else tree->nextComplete = 0; }

void First(ThreadBiTree *tree) { tree->current = tree->root; while(tree->current->leftThread == 0 tree->current = tree->current->leftChild;   if(tree->current == tree->root) tree->nextComplete = 1; else tree->nextComplete = 0; }

void Next(ThreadBiTree *tree) { ThreadBiNode *p = tree->current->rightChild; if(tree->nextComplete == 1) return; if(tree->current->rightThread == 0) while(p->leftThread == 0) p = p->leftChild; tree->current = p; if(tree->current == tree->root) tree->nextComplete = 1; }   int EndOfNext(ThreadBiTree *tree) { return tree->nextComplete;

例8-3 编写一个程序，首先建立如图8-10（a）所示的不带头结点的二叉树，然后中序线索化该二叉树，最后用循环结构输出该中序线索化二叉树各结点的序列信息。

void main(void) { ThreadBiNode *root; ThreadBiTree tree;   MakeCharTree(&root); CreatInThread(&root); printf("二叉树中序正向遍历序列为："); ThreadInitiate(&tree, root); /*循环初始化*/ for(First(&tree); !EndOfNext(&tree); Next(&tree)) printf("%c ", tree.current->data); }

8.6 哈夫曼树 1.哈夫曼树的基本概念 从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长度（WPL），即： WPL = 其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。

下图所示二叉树带权路径长度分别为: 1 3 5 7 ( a ) b c d

（a）WPL = 1×2+3×2+5×2+7×2 = 32 （b）WPL = 1×2+3×3+5×3+7×1 = 33 （c）WPL = 7×3+5×3+3×2+1×1 = 43 （d）WPL = 1×3+3×3+5×2+7×1 = 29 具有最小带权路径长度的二叉树称作哈夫曼（Huffman）树（或称最优二叉树）。图（d）的二叉树是一棵哈夫曼树。 定义：由给定的n个叶结点权值可以构造很多棵形态不同的二叉树，WPL值最小的二叉树称为哈夫曼树。 要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼树构造算法为：

（1）由给定的n个权值{w1,w2,…,wn}构造n棵只有根结点的二叉树，从而得到一个二叉树森林F={T1,T2,…,Tn}。 （3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。 （4）重复步骤（2）和（3），当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。

2.哈夫曼编码问题 将传送的文字转换为二进制字符0和1组成的二进制串的过程为编码。 例：假设要传送的电文为ABACCDA，电文中只有A,B,C,D四种字符，若这四个字符采用表(a)所示的编码方案，则电文的代码为00 01 00 10 10 11 00，代码总长度为14。若这四个字符采用表(b)所示的编码方案，则电文的代码为0 110 0 10 10 111 0，代码总长度为13。

字符 编码 A 00 B 01 C 10 D 11 字符 编码 A B 110 C 10 D 111 （b） （a）

哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。代码总长度最短的不等长编码称之为哈夫曼编码。 不等长编码不允许存在前缀码。前缀码的一个例子如：A为01，B为010。如编码存在前缀码，则译码会出现二义性。 问题：为什么哈夫曼编码一定不会出现前缀码？

3.哈夫曼编码的软件设计 一、哈夫曼编码的数据结构设计 为了在构造哈夫曼树时能方便的实现从双亲结点到左右孩子结点的操作，在进行哈夫曼编码时能方便的实现从孩子结点到双亲结点的操作。设计哈夫曼树的结点存储结构为双亲孩子存储结构。采用仿真指针实现，每个结点的数据结构设计为： weight flag parent leftChild rightChild

从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。存放哈夫曼编码的数据元素结构为： start Bit[0] Bit[1] … Bit[MaxBit-1]

二、哈夫曼编码的算法实现 typedef struct //哈夫曼树的结点结构 { int weight; //权值 int flag; //标记 int parent; //双亲结点下标 int leftChild; //左孩子下标 int rightChild; //右孩子下标 } HaffNode; typedef struct //存放哈夫曼编码的数据元素结构 { int bit[MaxN]; //数组 int start; //编码的起始下标 int weight; //字符的权值 } Code;

哈夫曼树构造算法如下： void Haffman(int weight[], int n, HaffNode haffTree[]) //建立叶结点个数为n权值为weight的哈夫曼树haffTree { int j, m1, m2, x1, x2;  //哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for(int i = 0; i < 2 * n - 1 ; i++) { if(i < n) haffTree[i].weight = weight[i]; else haffTree[i].weight = 0; haffTree[i].parent = -1; haffTree[i].flag = 0; haffTree[i].leftChild = -1; haffTree[i].rightChild = -1; }

//构造哈夫曼树haffTree的n-1个非叶结点 for(i = 0;i < n-1;i++) { m1 = m2 = MaxValue; x1 = x2 = 0; for(j = 0; j < n+i;j++) { if(haffTree[j].weight < m1 && haffTree[j].flag == 0) { m2 = m1; x2 = x1; m1 = haffTree[j].weight; x1 = j; } else if(haffTree[j].weight < m2 && haffTree[j].flag == 0) { m2 = haffTree[j].weight; x2 = j;

} //将找出的两棵权值最小的子树合并为一棵子树 haffTree[x1].parent = n+i; haffTree[x1].flag = 1; haffTree[x2].flag = 1; haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild = x1; haffTree[n+i].rightChild = x2; } }

哈夫曼编码算法如下： void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[]) { Code *cd = (Code *)malloc(sizeof(Code)); int i, j, child, parent;   /*求n个叶结点的哈夫曼编码*/ for(i = 0; i < n; i++) cd->start = n-1; cd->weight = haffTree[i].weight; child = i; parent = haffTree[child].parent;

if(haffTree[parent].leftChild == child) cd->bit[cd->start] = 0; /*由叶结点向上直到根结点*/ while(parent != -1) { if(haffTree[parent].leftChild == child) cd->bit[cd->start] = 0; else cd->bit[cd->start] = 1; cd->start--; child = parent; parent = haffTree[child].parent; } for(j = cd->start+1; j < n; j++) haffCode[i].bit[j] = cd->bit[j]; haffCode[i].start = cd->start + 1; haffCode[i].weight = cd->weight;

例：设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，则哈夫曼树构造过程如下图所示： 下标 weight leftChild rightChild parent flag 1 -1 3 2 5 7 4 6 （a）

下标 weight leftChild rightChild parent flag 1 -1 4 3 2 5 7 6 （b）第一步的结果

（c）第二步的结果 下标 weight leftChild rightChild parent flag 1 -1 4 3 2 5 7 9 1 -1 4 3 2 5 7 9 6 （c）第二步的结果

（d）哈夫曼树构造结果 下标 weight leftChild rightChild parent flag 1 -1 4 3 2 5 7 1 -1 4 3 2 5 7 6 9 16 （d）哈夫曼树构造结果

  1 3 2 5 7 0 1 2 3 bit start weight （e）哈夫曼编码结果

例8-5 设有字符集{A, B, C, D}，各字符在电文中出现的次数集为{1, 3, 5, 7}，设计各字符的哈夫曼编码。 #include <stdio.h> #include <stdlib.h> #define MaxValue 10000 #define MaxBit 4 #define MaxN 100 #include "Haffman.h"

void main(void) { int i, j, n = 4; int weight[] = {1,3,5,7};   HaffNode *myHaffTree = (HaffNode *)malloc(sizeof(HaffNode)*(2*n-1)); Code *myHaffCode = (Code *)malloc(sizeof(Code)*n); if(n > MaxN) { printf("给出的n越界，修改MaxN值!\n"); exit(0); } Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode);   /*输出每个叶结点的哈夫曼编码*/ for(i = 0; i < n; i++) { printf("Weight = %d Code = ", myHaffCode[i].weight); for(j = myHaffCode[i].start; j < n; j++) printf("%d", myHaffCode[i].bit[j]); printf("\n");

该结果和图8-15所示的该问题的人工设计的哈夫曼编码方案完全吻合。 程序运行输出结果如下： Weight = 1 Code = 100 Weight = 3 Code = 101 Weight = 5 Code = 11 Weight = 7 Code = 0 该结果和图8-15所示的该问题的人工设计的哈夫曼编码方案完全吻合。

8.7 等价问题 1．等价关系和等价类 若集合X上的关系R是自反的、对称的和传递的，则称关系R是集合X上的等价关系。 设关系R为定义在集合X上的二元关系，若对于每一个x∈X，都有(x,x)∈R，则称R是自反的。例如，相等关系就是自反关系。 设关系R为定义在集合X上的二元关系，若对于任意的x,y∈X，若当(x,y)∈R时，有(y,x)∈R，则称R是对称的。例如，相等关系就是对称关系。

设关系R为定义在集合X上的二元关系，如果对于任意的x,y,z∈X，若当(x,y)∈R且(y,z)∈R时，有(x,z)∈R，则称关系R是传递的。例如，设集合X={1,2,3}，关系R={(1,2),(2,3),(1,3)}，则关系R是传递的。另外，相等关系也是传递关系。 等价关系的实质是将集合中的元素分类。 若关系R是集合X上的一个等价关系，则可以按R将集合X划分成若干互不相交的子集X1,X2,X3,…，这些子集的并X1∩X2∩X3∩…为集合X，则这些子集便称为集合X的关于R的等价类。

2．等价类的应用 许多应用问题可以归结为按给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。 例如，要测试一个软件是否存在问题，这个软件所有允许的输入数据构成了集合，这个集合中的元素通常很多。我们把软件所有允许的输入数据域划分成若干子集合，然后从每一个子集合中选取少数具有代表性的数据作为测试用例。这样的测试用例设计方法可以有效地避免大量的冗余测试。这种方法是一种常用的软件黑盒测试用例设计方法。

3．确定等价类的并查算法 并查（UNION/FIND）算法是确定等价类的有效算法。并查算法思想是： （1）令有n个元素的集合X中的每个元素各自构成一个只含单个元素的子集X1,X2,X3,…,Xn； （2）重复读入m个等价对(x,y)。对于每个读入的等价对(x,y)，设x∈Xi，y∈Xj，如果Xi＝Xj，则不做任何操作；如果Xi≠Xj，则将Xj并入Xi，并将Xj置为空（或将Xi并入Xj，并将Xi置为空）。 。

则上述算法执行完后，子集合X1,X2,X3,…,Xn中所有非空子集合即为X的关于等价关系R的等价类。 上述算法之所以称为并查算法，是因为该算法主要由并操作和查操作组成。查操作完成判定某个元素所在子集，并操作完成两个互不相交子集的合并

4．等价类与树结构 等价类可以采用树结构表示。用一棵树代表一个集合，如果两个结点在同一棵树中，则认为这两个结点在同一个集合中。 用树结构表示的等价类，大多数情况下，其存储方法采用双亲表示法。具体的存储结构可以采用元素集合存储在一个数组中，所有相同的等价类放在同一个根结点的树中，树用双亲表示法表示。 例8-5 设集合X={x|1≤x≤10，且x是整数}，R是X上的等价关系。 R = {(1,3),(3,5),(3,7),(2,4),(4,6),(2,8)} 求出集合X的关于R的等价类，并画出存储结构示意图。 说明：这里省略了类如(1,1)的自反关系、类如(3,1)的对称关系以及类如(1,5)的部分传递关系。

1 3 5 7 2 4 8 6 9 10

例8-6 根据前面讨论的并查算法，设计一个程序，完成例8-5的等价类建立。 typedef struct { int data; //数据元素 int parent; //双亲结点 }ESet; void Initialize(ESet x[], int n)//初始化 for(int e = 1; e <= n; e++) { x[e].data = e; x[e].parent = -1; }

int Find(ESet x[], int i) //查 { int e = i; while(x[e].parent >= 0) e = x[e].parent; //上移一层 return e; } void Union(ESet x[], int i, int j) //并 { x[j].parent = i; int e = Find(x, i); x[e].parent = x[e].parent - 1;//累加

void main(void) { int n =10; ESet *x = new ESet[n+1]; Initialize(x, n); if( Find(x, 1) != Find(x, 3)) Union(x, 1, 3); if( Find(x, 3) != Find(x, 5)) Union(x, 3, 5); if( Find(x, 3) != Find(x, 7)) Union(x, 3, 7); if( Find(x, 2) != Find(x, 4)) Union(x, 2, 4); if( Find(x, 4) != Find(x, 6)) Union(x, 4, 6); if( Find(x, 2) != Find(x, 8)) Union(x, 2, 8); for(int e = 1; e <= n; e++) cout << x[e].data << " " << x[e].parent << endl; }

程序运行的输出结果如下： 1 -4 2 -4 3 1 4 2 5 3 6 4 7 3 8 2 9 -1 10 -1 程序运行的输出结果和图8-17（c）所示的等价类树完全相同。

8.8 树与二叉树的转换 1.树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线。 （2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线。 （3）整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。

（a）树;（b）相临兄弟加连线;（c）删除双亲与非第一个孩子连线;（d）二叉树 E F G ( a ) b c d 树转换为二叉树的过程 （a）树;（b）相临兄弟加连线;（c）删除双亲与非第一个孩子连线;（d）二叉树

2.二叉树还原为树 二叉树还原为树的方法是： （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。 （2）删除原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。

（a）二叉树;（b）双亲与非第一个孩子加连线; E F C D G ( a ) b c d 二叉树还原为树的过程 （a）二叉树;（b）双亲与非第一个孩子加连线; （c）删除结点与右孩子连线;（d）树

8.9 树的遍历 树的遍历操作是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历算法主要有先根遍历算法和后根遍历算法两种。因为树是递归定义的，因此树的遍历算法都可以设计成递归算法。 1.先根遍历 树的先根遍历递归算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。

上图中所示树，先根遍历得到的结点序列为： A B E J F C G K L D H I 注意：树的先根遍历序列一定和该树转换的二叉树的先序遍历序列相同。 问题：为什么？

2.后根遍历 树的后根遍历递归算法为： （1）按照从左到右的次序后根遍历根结点的每一棵子树； （2）访问根结点。 上页图中所示树，后根遍历得到的结点序列为： J E F B K L G C H I D A 注意：树的后根遍历序列一定和该树转换的二叉树的中序遍历序列相同。 问题：为什么？

作业 1) 习题8-3，8-5 2) 习题8-4 ，8-17 ，8-24 3) 习题8-6，8-31 4)习题8-7，8-18 ，8-23 ，8-32 5)叙述并查算法思想 举例说明等价类的应用 6)习题8-22，8-26