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

1,数据结构及应用算法教程(修订版),配套课件,2,第6章 二叉树和树,前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。 二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。 讲授本章课程大约需8课时。,3,6.4 树的应用,一、堆排序的实现 二、二叉排序树 三、赫夫曼树及其应用,4,一、堆排序的实现,5,堆是满足下列性质的数列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章排序,6,ri,r2i,r2i+1,若将该数列视作完全二叉树， 则 r2i 是 ri 的左孩子; r2i+1 是 ri 的右孩子。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,7,如何“建堆”？,两个问题:,如何“筛选”？,定义堆类型为:,typedef SqList HeapType; / 堆采用顺序表表示之,HeapAdjust (., ., .);,8,所谓“筛选”指的是，对一棵左/右子树 均为堆的完全二叉树，“调整”根结点 使整个二叉树也成为一个堆。,筛选,9,98,81,49,73,55,64,12,36,27,40,例如:,是大顶堆,12,但在 98 和 12 进行互换之后，它就不是堆了,因此，需要对它进行“筛选”,98,12,81,73,64,12,98,比较,比较,10,void HeapAdjust (RcdType &R, int s, int m) / 已知 Rsm中记录的关键字除 Rs 之外均 / 满足堆的特征，本函数自上而下调整 Rs 的 / 关键字，使 Rsm 也成为一个大顶堆 / HeapAdjust,rc = Rs; / 暂存 Rs,for ( j=2*s; j=m; j*=2 ) / j 初值指向左孩子 自上而下的筛选过程; ,Rs = rc; / 将调整前的堆顶记录插入到 s 位置,11,if ( rc.key = Rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整,Rs = Rj; s = j; / 否则记录上移，尚需继续往下调整,if ( jm / 左/右“子树根”之间先进行相互比较 / 令 j 指示关键字较大记录的位置,自上而下的筛选过程的代码段：,12,建堆是一个从下往上进行“筛选”的反复过程,40,55,49,73,81,64,36,12,27,98,例如: 排序之前的关键字序列为,12,36,81,73,49,98,81,73,55,现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。,98,49,40,64,36,12,27,13,void HeapSort ( HeapType &H ) / 对顺序表 H 进行堆排序。 / HeapSort,for ( i=H.length/2; i0; -i ) / 建大顶堆 HeapAdjust ( H.r, i, H.length );,for ( i=H.length; i1; -i ) / 调整堆来实现排序 H.r1H.ri; / 将堆顶记录和当前未经排序子序列 / H.r1i中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); / 对 H.r1 进行筛选 ,14,堆排序的逻辑结构是一棵完全二叉树，而实现的空间则是顺序表。以数据模型演示数据在顺序空间的动态变化。,初始堆的建立过程：,初始堆的建立过程有比较大的消耗，可达4n,15,堆排序第一趟：,81,堆排序第二趟：,73,堆排序第三趟：,64,可以看出，每趟的调整只牵涉少量的数据,16,堆排序的时间复杂度分析( 建堆+ n-1 次调整)：,以后的每次调整，耗费将显著减少。因为这样调整所耗用的比较操作次数都不超过堆的树深，是一种消耗很少的局部调整。,初始堆的建立过程:O (n),建成深度为 h = (log2n+1) 的堆,需要调整n-1次，总共进行的关键字比较的次数不超过 2*(log2(n-1)+ log2(n-2)+ +log22) 2n(log2n),因此，堆排序的时间复杂度为O(nlogn),17,二、二叉排序树,18,（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；,1二叉排序的定义：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；,19,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序树。,66,不,20,（49，38，65，76，49，13，27，52）,构造二叉排序树,构建二叉排序树的过程，是一个从空树起不断插入结点的过程。每插入一个结点都应保证遵从二叉排序树的定义。,21,（ ， ， ， ， ， ， ， ）,13,27,38,49,49,52,65,76,中序遍历二叉排序树,如果中序遍历二叉排序树，所得序列将是有序的，即实现了对原始数据的排序，二叉排序树即由此得名。,22,有关二叉排序树更详细的讨论及算法，请见第8章查找表的二叉查找树一节,23,三、赫夫曼树及其应用,最优树的定义 如何构造最优树 前缀编码,24,最优树的定义,树的路径长度定义为： 树中每个结点的路径长度之和。,结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。,25,树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)。,在所有含 n 个叶子结点、并带相同权 值的 m 叉树中, 必存在一棵其带权路径 长度取最小值的树，称为“最优树”。,例如：,26,2,7 9,7,5,4,9,2,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5,4,27,根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；,如何构造最优树,(1),(赫夫曼算法) 以二叉树为例：,28,在 F 中选取其根结点的权值为最小 的两棵二叉树，分别作为左、右子 树构造一棵新的二叉树，并置这棵 新的二叉树根结点的权值为其左、 右子树根结点的权值之和；,(2),29,从F中删去这两棵树，同时加入 刚生成的新树；,重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。,(3),(4),30,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,31,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,32,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。,33,出现频度: 5, 6, 2, 9, 7,编码: 101, 00, 100, 11, 01,字母集: s, t, a, e, i,电文: eat,编码 : e a t,11,100,00,译电文: eat,符合前缀编码规则才能按唯一性进行译码,34,本章学习要点,35,1. 熟练掌握二叉树的结构特性，了解相应性质的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。,36,4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟悉二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。,37,5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 6. 学会编写实现树的各种操作的算法。 7. 深刻理解二叉排序树的定义及特性。 8. 熟练掌握堆排序的算法。 9.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,38,习题解答实例,39,算法设计题6-20 将二叉排序树输出到一个空的循环链表，要求： （1）使链表结点的值按降序排列； （2）使链表结点的值按升序排列。,按中序遍历二叉排序树，可以得到按升序排列的输出。如果从链表的前部逐一插入就得到降序排列。,40,void degression (BSTree T, LinkList ,new(s); s-data = T -data; s-next = head-next; head-next = s;,38,（1）使链表结点的值按降序排列算法：,插入结点的指针操作,41,49,38,13,40,13,38,40,76,49,降序排列的动态模型演示,42,要利用从前部插入操作操作简单的优点，又要得到升序排列的结构，就要求输出的序列本身为降序。只需在中序遍历二叉排序树时改变“先左后右”的次序，按“先右后左”进行遍历。,43,void increase (BSTree T, LinkList ,T -rchild,T -lchild,调换了遍历的次序,（2）使链表结点的值按升序排列算法：,44,49,38,13,40,76,49,40,13,38,升序排列的动态模型演示,45,算法设计题6-24 以广义表的字符串的形式输出“孩子-兄弟链表”作存储结构的树。,前序遍历“孩子-兄弟链表”表示的树，在该算法中的适当位置加入输出“（”、“）”和“，”的语句，即可实现广义表的字符串的形式输出。,46,A,B,C,D,E,G,F,F,void preOrderTree (CSTree T) if (T) visit (T); / 访问当前的根结点 for (p= T-firstchild; p; p= p-nextsibling ) preOrderTree (p); ,存储表示为“孩子-兄弟链表” 树的前序遍历,47,void outputTree (CSTree T) if (T) printf(“%c“,T-data); / 输出当前结点的数据域值 if (T-firstchild) printf(“(“); / 左孩子不空打印左括弧“（” for(p= T-firstchild; p; p=