数据结构及应用算法教程修订版

a1数据结构及应用算法教程(修订版)配套课件数据结构及应用算法教程修订版全文共49页，当前为第1页。a2第6章二叉树和树

前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。讲授本章课程大约需8课时。数据结构及应用算法教程修订版全文共49页，当前为第2页。a3

6.4树的应用

一、堆排序的实现二、二叉排序树三、赫夫曼树及其应用数据结构及应用算法教程修订版全文共49页，当前为第3页。a4一、堆排序的实现数据结构及应用算法教程修订版全文共49页，当前为第4页。a5堆是满足下列性质的数列{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}不是堆(小顶堆)(大顶堆)复习第4章排序数据结构及应用算法教程修订版全文共49页，当前为第5页。a6rir2ir2i+1

若将该数列视作完全二叉树，则r2i

是ri

的左孩子;r2i+1

是

ri

的右孩子。1236276549817355403498例如:是堆14不数据结构及应用算法教程修订版全文共49页，当前为第6页。a7如何“建堆”？两个问题:如何“筛选”？定义堆类型为:typedef

SqListHeapType;//堆采用顺序表表示之HeapAdjust(.,.,.);数据结构及应用算法教程修订版全文共49页，当前为第7页。a8

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

筛选堆堆数据结构及应用算法教程修订版全文共49页，当前为第8页。a998814973556412362740例如:是大顶堆12但在98

和12

进行互换之后，它就不是堆了因此，需要对它进行“筛选”98128173641298比较比较数据结构及应用算法教程修订版全文共49页，当前为第9页。a10void

HeapAdjust(RcdType&R[],int

s,int

m){//已知R[s..m]中记录的关键字除R[s]之外均

//满足堆的特征，本函数自上而下调整R[s]的

//关键字，使R[s..m]也成为一个大顶堆}//HeapAdjustrc=R[s];//暂存R[s]for

(j=2*s;j<=m;j*=2

){//j初值指向左孩子

自上而下的筛选过程;}R[s]=rc;

//将调整前的堆顶记录插入到s位置数据结构及应用算法教程修订版全文共49页，当前为第10页。a11if(rc.key>=R[j].key)break;//再作“根”和“子树根”之间的比较，

//若“>=”成立，则说明已找到rc的插

//入位置s，不需要继续往下调整R[s]=R[j];s=j;

//否则记录上移，尚需继续往下调整if(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子树根”之间先进行相互比较

//令j指示关键字较大记录的位置自上而下的筛选过程的代码段：数据结构及应用算法教程修订版全文共49页，当前为第11页。a12

建堆是一个从下往上进行“筛选”的反复过程40554973816436122798例如:排序之前的关键字序列为123681734998817355

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。98494064361227数据结构及应用算法教程修订版全文共49页，当前为第12页。a13voidHeapSort(HeapType&H){

//对顺序表H进行堆排序。}

//HeapSortfor

(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]进行筛选}数据结构及应用算法教程修订版全文共49页，当前为第13页。a1412345678910405549731227988164363612738181559849557340984049

堆排序的逻辑结构是一棵完全二叉树，而实现的空间则是顺序表。以数据模型演示数据在顺序空间的动态变化。初始堆的建立过程：初始堆的建立过程有比较大的消耗，可达4n数据结构及应用算法教程修订版全文共49页，当前为第14页。a15堆排序第一趟：1234567891098814973362740556412129881127312641281堆排序第二趟：123456789108173496436274055121298128112731264125573堆排序第三趟：1234567891073644955362740128112988173121264125564可以看出，每趟的调整只牵涉少量的数据……

有序段数据结构及应用算法教程修订版全文共49页，当前为第15页。a16堆排序的时间复杂度分析(建堆+

n-1

次调整)：

以后的每次调整，耗费将显著减少。因为这样调整所耗用的比较操作次数都不超过堆的树深，是一种消耗很少的局部调整。

初始堆的建立过程:O(n)建成深度为

h=(log2n+1)的堆,需要调整n-1次，总共进行的关键字比较的次数不超过

2*(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)

因此，堆排序的时间复杂度为O(nlogn)数据结构及应用算法教程修订版全文共49页，当前为第16页。a17二、二叉排序树

数据结构及应用算法教程修订版全文共49页，当前为第17页。a18（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．二叉排序的定义：

二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；数据结构及应用算法教程修订版全文共49页，当前为第18页。a19503080209010854035252388例如:是二叉排序树。66不数据结构及应用算法教程修订版全文共49页，当前为第19页。a20（49，38，65，76，49，13，27，52）4938657649132752构造二叉排序树

构建二叉排序树的过程，是一个从空树起不断插入结点的过程。每插入一个结点都应保证遵从二叉排序树的定义。数据结构及应用算法教程修订版全文共49页，当前为第20页。a21（，，，，，，，）1327384949526576（49，38，65，76，49，13，27，52）原始序列数据4938657649132752构造的二叉排序树中序遍历二叉排序树

如果中序遍历二叉排序树，所得序列将是有序的，即实现了对原始数据的排序，二叉排序树即由此得名。数据结构及应用算法教程修订版全文共49页，当前为第21页。a22

有关二叉排序树更详细的讨论及算法，请见第8章查找表的二叉查找树一节数据结构及应用算法教程修订版全文共49页，当前为第22页。a23三、赫夫曼树及其应用最优树的定义如何构造最优树前缀编码数据结构及应用算法教程修订版全文共49页，当前为第23页。a24

最优树的定义树的路径长度定义为：

树中每个结点的路径长度之和。

结点的路径长度定义为：

从根结点到该结点的路径上分支的数目。数据结构及应用算法教程修订版全文共49页，当前为第24页。a25

树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和

WPL(T)=wklk(对所有叶子结点)。

在所有含n个叶子结点、并带相同权值的m叉树中,必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：数据结构及应用算法教程修订版全文共49页，当前为第25页。a2627975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954数据结构及应用算法教程修订版全文共49页，当前为第26页。a27

根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合

F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；如何构造最优树(1)(赫夫曼算法)以二叉树为例：数据结构及应用算法教程修订版全文共49页，当前为第27页。a28

在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；(2)数据结构及应用算法教程修订版全文共49页，当前为第28页。a29

从F中删去这两棵树，同时加入刚生成的新树；

重复(2)

和(3)

两步，直至F中只含一棵树为止。(3)(4)数据结构及应用算法教程修订版全文共49页，当前为第29页。a309例如:已知权值W={

5,6,2,9,7

}562752769767139527数据结构及应用算法教程修订版全文共49页，当前为第30页。a316713952795271667132900001111000110110111数据结构及应用算法教程修订版全文共49页，当前为第31页。a32

指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。前缀编码

利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。数据结构及应用算法教程修订版全文共49页，当前为第32页。a33出现频度:5,6,2,9,7编码:

101,00,100,11,01字母集:

s,t,a,e,i电文:eat编码:eat111000025701100101911160167130100012901tiase译电文:eat

符合前缀编码规则才能按唯一性进行译码数据结构及应用算法教程修订版全文共49页，当前为第33页。a34本章学习要点数据结构及应用算法教程修订版全文共49页，当前为第34页。a35

1.熟练掌握二叉树的结构特性，了解相应性质的证明方法。

2.熟悉二叉树的各种存储结构的特点及适用范围。

3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。数据结构及应用算法教程修订版全文共49页，当前为第35页。a36

4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟悉二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。数据结构及应用算法教程修订版全文共49页，当前为第36页。a37

5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。

6.学会编写实现树的各种操作的算法。

7.深刻理解二叉排序树的定义及特性。

8.熟练掌握堆排序的算法。

9.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。数据结构及应用算法教程修订版全文共49页，当前为第37页。a38习题解答实例数据结构及应用算法教程修订版全文共49页，当前为第38页。a39

算法设计题6-20

将二叉排序树输出到一个空的循环链表，要求：（1）使链表结点的值按降序排列；（2）使链表结点的值按升序排列。

按中序遍历二叉排序树，可以得到按升序排列的输出。如果从链表的前部逐一插入就得到降序排列。数据结构及应用算法教程修订版全文共49页，当前为第39页。a40void

degression(BSTreeT,LinkList&head)

{if（T）{

degression(T->lchild);

degression(T->rchild);

}}new(s);s->data=T->data;s->next=head->next;head->next=s;s13head38（1）使链表结点的值按降序排列算法：

插入结点的指针操作数据结构及应用算法教程修订版全文共49页，当前为第40页。a4149387613401313381338401338404976133840491338407649降序排列的动态模型演示数据结构及应用算法教程修订版全文共49页，当前为第41页。a42

要利用从前部插入操作操作简单的优点，又要得到升序排列的结构，就要求输出的序列本身为降序。只需在中序遍历二叉排序树时改变“先左后右”的次序，按“先右后左”进行遍历。数据结构及应用算法教程修订版全文共49页，当前为第42页。a43void

increase(BSTreeT,LinkList&head)

{if（T）{

increase();

new(s);s->data=T->data;s->next=head->next;head->next=s;

increase();

}}T->rchildT->lchild

调换了遍历的次序（2）使链表结点的值按升序排列算法：数据结构及应用算法教程修订版全文共49页，当前为第43页。a4449387613407676497649407649403813764940387649401338升序排列的动态模型演示数据结构及应用算法教程修订版全文共49页，当前为第44页。a45

算法设计题6-24

以广义表的字符串的形式输出“孩子-兄弟链表”作存储结构的树。

前序遍历“孩子-兄弟链表”表示的树，在该算法中的适当位置加入输出“（”、“）”和“，”的语句，即可实现广义表的字符串的形式输出。数据结构及应用算法教程修订版全文共49页，当前为第45页。a46ABCDEGFFABCDEFHGvoidpreOrderTree(CSTreeT)

{

if

(T)

{

visit(T);

//访问当前的根结点

for(p=T->firstchild;p;p=p->nextsibling)

preOrderTree(p);

}}存储表示为“孩子-兄弟链表”树的前序遍历数据结构及应用算法教程修订版全文共49页，当前为第46页。a47voidoutputTree(CSTreeT){

if(T){printf("%c",T->data);//输出当前结点的数据域值

if(T->firstchild){

printf("(");//左孩子不空打印左括弧“（”

for(p=T->firstchild;p;