数据结构及应用算法教程(修订版) 配套课件

第6章 二叉树和树 前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。 二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。 讲授本章课程大约需8课时。

6.4 树的应用 一、堆排序的实现 二、二叉排序树 三、赫夫曼树及其应用

一、堆排序的实现

堆的定义: 复习第4章排序 堆是满足下列性质的数列{r1, r2, …，rn}： 或 例如: 是小顶堆 不是堆 (小顶堆) (大顶堆) {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆

不 ri r2i r2i+1 若将该数列视作完全二叉树， 则 r2i 是 ri 的左孩子; r2i+1 是 ri 的右孩子。 例如: 是堆 12 36 27 65 40 14 34 98 不 是堆 81 73 55 49

两个问题: 定义堆类型为: 如何“建堆”？ 如何“筛选”？ typedef SqList HeapType; // 堆采用顺序表表示之 HeapAdjust (., ., .); 如何“筛选”？

所谓“筛选”指的是，对一棵左/右子树 均为堆的完全二叉树，“调整”根结点 使整个二叉树也成为一个堆。 堆 堆 筛选

例如: 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了 因此，需要对它进行“筛选” 12 12 81 98 73 81 49 比较 12 81 98 比较 73 81 49 64 73 36 27 40 55 64 12 98 12 98 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了 因此，需要对它进行“筛选”

void HeapAdjust (RcdType &R[], int s, int m) { // 已知 R[s..m]中记录的关键字除 R[s] 之外均 // 满足堆的特征，本函数自上而下调整 R[s] 的 // 关键字，使 R[s..m] 也成为一个大顶堆 } // HeapAdjust rc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ){ // j 初值指向左孩子 自上而下的筛选过程; } R[s] = rc; // 将调整前的堆顶记录插入到 s 位置

自上而下的筛选过程的代码段： if ( j<m && R[j].key<R[j+1].key ) ++j; // 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较大记录的位置 if ( rc.key >= R[j].key ) break; // 再作“根”和“子树根”之间的比较， // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整 R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整

建堆是一个从下往上进行“筛选”的反复过程 例如: 排序之前的关键字序列为 40 98 81 55 98 49 49 73 81 73 36 12 36 27 27 98 40 49 81 55 73 64 64 12 12 36 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。

void HeapSort ( HeapType &H ) { // 对顺序表 H 进行堆排序。 for ( i=H.length/2; i>0; --i ) // 建大顶堆 HeapAdjust ( H.r, i, H.length ); for ( i=H.length; i>1; --i ) { // 调整堆来实现排序 H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 }

初始堆的建立过程有比较大的消耗，可达4n 堆排序的逻辑结构是一棵完全二叉树，而实现的空间则是顺序表。以数据模型演示数据在顺序空间的动态变化。 初始堆的建立过程： 1 2 3 4 5 6 7 8 9 10 40 55 49 73 12 27 98 81 64 36 40 98 81 55 40 49 98 49 55 73 73 81 36 12 初始堆的建立过程有比较大的消耗，可达4n

堆排序第一趟： 1 2 3 4 5 6 7 8 9 10 98 81 49 73 36 27 40 55 64 12 81 12 12 98 81 73 12 64 12 堆排序第二趟： 1 2 3 4 5 6 7 8 9 10 81 73 49 64 36 27 40 55 12 98 73 12 81 12 73 12 64 12 55 堆排序第三趟： 1 2 3 4 5 6 7 8 9 10 73 64 49 55 36 27 40 12 81 98 64 12 64 73 12 12 55 …… 有序段 可以看出，每趟的调整只牵涉少量的数据

堆排序的时间复杂度分析( 建堆+ n-1 次调整)： 初始堆的建立过程:O (n) 以后的每次调整，耗费将显著减少。因为这样调整所耗用的比较操作次数都不超过堆的树深，是一种消耗很少的局部调整。 建成深度为 h = (log2n+1) 的堆,需要调整n-1次，总共进行的关键字比较的次数不超过 2*(log2(n-1)+ log2(n-2)+ …+log22) < 2n(log2n) 因此，堆排序的时间复杂度为O(nlogn)

二、二叉排序树

1．二叉排序的定义： 二叉排序树或者是一棵空树；或者是具有如下特性的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值； （3）它的左、右子树也都分别是二叉排序树。

例如: 50 30 80 20 40 90 10 25 35 85 66 23 88 不 是二叉排序树。

构建二叉排序树的过程，是一个从空树起不断插入结点的过程。每插入一个结点都应保证遵从二叉排序树的定义。 （49，38，65，76，49，13，27，52） 49 38 65 76 49 13 27 52 构造二叉排序树

如果中序遍历二叉排序树，所得序列将是有序的，即实现了对原始数据的排序，二叉排序树即由此得名。 （49，38，65，76，49，13，27，52） 原始序列数据 49 38 65 76 13 27 52 构造的二叉排序树 中序遍历二叉排序树 （ ， ， ， ， ， ， ， ） 13 27 38 49 49 52 65 76

有关二叉排序树更详细的讨论及算法，请见第8章查找表的二叉查找树一节

三、赫夫曼树及其应用 最优树的定义 如何构造最优树 前缀编码

最优树的定义 结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的路径长度定义为： 树中每个结点的路径长度之和。

树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。 例如： 在所有含 n 个叶子结点、并带相同权 值的 m 叉树中, 必存在一棵其带权路径 长度取最小值的树，称为“最优树”。

2 4 7 5 9 5 4 2 7 9 WPL(T)= 72+52+23+43+92 =60 WPL(T)= 74+94+53+42+21 =89

如何构造最优树 (赫夫曼算法) 以二叉树为例： (1) 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 n 棵二叉树的集合 (赫夫曼算法) 以二叉树为例： 根据给定的 n 个权值 {w1, w2, …, wn}， 构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树； (1)

在 F 中选取其根结点的权值为最小 (2) 的两棵二叉树，分别作为左、右子 树构造一棵新的二叉树，并置这棵 新的二叉树根结点的权值为其左、 右子树根结点的权值之和； (2)

从F中删去这两棵树，同时加入 刚生成的新树； (3) 重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。 (4)

例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7 6 9 7 7 5 2 9 7 13 5 2 6 7

9 7 13 5 2 6 7 29 1 13 16 1 1 6 7 9 7 1 00 01 10 5 2 110 111

前缀编码 指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。 利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。

字母集: s, t, a, e, i 出现频度: 5, 6, 2, 9, 7 编码: 101, 00, 100, 11, 01 2 5 7 1 100 101 9 11 16 6 13 00 01 29 电文: eat 编码 : e a t 11 100 00 译电文: eat 符合前缀编码规则才能按唯一性进行译码 t i a s e

本章学习要点

　1. 熟练掌握二叉树的结构特性，了解相应性质的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟悉二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。

　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　6. 学会编写实现树的各种操作的算法。 　7. 深刻理解二叉排序树的定义及特性。 8. 熟练掌握堆排序的算法。 9.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。

习题解答实例

算法设计题6-20 将二叉排序树输出到一个空的循环链表，要求： （1）使链表结点的值按降序排列； （2）使链表结点的值按升序排列。 按中序遍历二叉排序树，可以得到按升序排列的输出。如果从链表的前部逐一插入就得到降序排列。

（1）使链表结点的值按降序排列算法： void degression (BSTree T, LinkList &head) { if（T）{ degression(T ->lchild ); degression(T ->rchild ); } 13 head new(s); s->data = T ->data; s->next = head->next; head->next = s; s 38 插入结点的指针操作

降序排列的动态模型演示 49 49 76 38 38 76 40 40 13 13 13 38 40 13 13 38 13 38 40 49 76 13 38 40 49

要利用从前部插入操作操作简单的优点，又要得到升序排列的结构，就要求输出的序列本身为降序。只需在中序遍历二叉排序树时改变“先左后右”的次序，按“先右后左”进行遍历。

（2）使链表结点的值按升序排列算法： 调换了遍历的次序 void increase (BSTree T, LinkList &head) { if（T）{ increase ( ); new(s); s->data = T ->data; s->next = head->next; head->next = s; } T ->lchild 调换了遍历的次序 T ->rchild

升序排列的动态模型演示 49 49 76 38 38 76 40 40 13 13 76 49 40 76 76 49 76 49 40 38 13 76 49 40 38

算法设计题6-24 以广义表的字符串的形式输出“孩子-兄弟链表”作存储结构的树。 前序遍历“孩子-兄弟链表”表示的树，在该算法中的适当位置加入输出“（”、“）”和“，”的语句，即可实现广义表的字符串的形式输出。

存储表示为“孩子-兄弟链表” 树的前序遍历 A A B C D E F H G B C E D F G F void preOrderTree (CSTree T) { if (T) { visit (T); // 访问当前的根结点 for (p= T->firstchild; p; p= p->nextsibling ) preOrderTree (p); }

void outputTree (CSTree T) { if (T) { printf("%c",T->data); // 输出当前结点的数据域值 if (T->firstchild) { printf("("); // 左孩子不空打印左括弧“（” for(p= T->firstchild; p; p= p->nextsibling ) { outputTree (p); // 递归遍历子树，实现子树的打印输出 if (p->nextsibling) printf(","); // 右兄弟不空，用逗号“，”分割子树的打印输出 } printf(")"); // 遇到最后的右兄弟，打印右括弧“）” if (T->firstchild) { printf("("); // 左孩子不空打印左括弧“（” { // 递归遍历子树，实现子树的打印输出 if (p->nextsibling) printf(","); // 右兄弟不空，用逗号“，”分割子树的打印输出 } printf(")"); // 遇到最后的右兄弟，打印右括弧“）” //在适当位置添加输出语句,改造前序遍历的算法

输出过程的动态模型演示 A A ( B B , C C ( , E E D D ) ( , ( F F ) G G ) H H )

第9次书面作业 6.26 第15次上机作业 实现算法6.14,6.15