数据结构第6章树的查找和树的应用课件

1、主要教学目标：了解查找树，掌握堆和堆排序的过程和算法；掌握平衡树的构造原理；掌握建立哈夫曼树和哈夫曼编码的方法。教学方法及教学手段：理论讲授与上机实践相结合教学重点及难点：建堆，堆排序，构造平衡树，构造哈夫曼树第六章 树的查找和树的应用6.1 查找树定义查找树，或是一棵空树，或具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树二叉排序树的插入插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止

2、，则插入结点应为该叶子结点的左孩子或右孩子二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树例 10， 18， 3， 8， 12， 2， 7， 31010181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列查找树的删除要删除查找树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULLp只有左子树或右子树p只有左子树，用p的左孩子代替p (1)(2)p只有右子树，用p的右孩子代替p (3)(4)p左、右子树均非空沿

3、p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5)若C无右子树，用C取代p (6)SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRPFPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍

4、历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)例805012060110150557053删除508060120110150557053删除60805512011015053701042581354删除1084255134删除584254131042581354删除1084255134删除5842541330 78 53 6 18 10 11 20 4947 15 34 56 90 61 5 20 87 416.2 满树、拟满树和丰满树定义满树：每层结点数达到最大个数拟满树：深度为k的二叉树，前k-1层是满树，第k层从左到右依次排列丰满树：深度为k的二叉树，前k-1层

5、是满树，第k层任意排列6.3 堆和堆排序堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成拟满树，则堆顶元素（拟满树的根）必为序列中n个元素的最小值或最大值堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这

6、个过程叫堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 2

7、7 384965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 657665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 5

8、0 65 76 97第一个问题解决方法方法：构造一棵拟满树，从最后一个根开始调整成堆结构，直至到根例 含8个元素的无序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650976.4 平衡树定义树的高度 设T是一棵二叉树,h(T)表示树T的高度.则 h(T)=maxh(Tl,Tr)+1平衡度(k)=h(Tkr)-h(Tkl)平衡树 二叉树中每个结点k都有|(k)= |1平衡查找树 树T既是查找树,又是平衡树 1、按查找树插入2、调整LL型

9、新结点插入a结点的左孩子b的左子树中，使a失去平衡，则 ，其余结点按查找树调整abba1、按查找树插入2、调整RR型 新结点插入a结点的右孩子b的右子树中，使a失去平衡，则 ，其余结点按查找树调整abba1、按查找树插入2、调整LR型 新结点插入a结点的左孩子b的右子树中，使a失去平衡，则 ，其余结点按查找树调整abb的右孩子ab1、按查找树插入2、调整RL型 新结点插入a结点的右孩子b的左子树中，使a失去平衡，则 ，其余结点按查找树调整abb的左孩子ba例：按G,F,A,D,C,E,B的顺序构造一棵平衡查找树G0G-1F0G-2F-1A0A1F-1D0G0F0A0G0A2F-2D-1G0C0

10、F-1C0G0A0D0例：按G,F,A,D,C,E,B的顺序构造一棵平衡查找树F-2C1G0A0D1E0D0C-1A0F0E0G0D-1C-2A1F0E0G0B0C0A0B0F0E0G0D06.5 最佳查找树Cij=Wij+Cik-1+Ckj=Wij+minCit-1+Ctj (ik j)Wij=Wij-1+pj+qj其中,Cii=0,rii=0,Wii=qi则左子树Tlij=Tit，右子树Trij=Ttj，rij=kit j6.6 二叉树的应用哈夫曼树(Huffman)带权路径长度最短的树定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径长度：路径上的分支数树的路径长度：从

11、树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和Huffman树设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35构造Huffman树的方法Huffman算法构造Huffman树步骤根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj在森林

12、中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5, 29, 7, 8, 14, 23, 3, 115142978233111429782311358871514292335811113581914292387151135819292314871529291487152911358192342113581923422914871529581135

13、8192342291487152958100lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0kx1=3,x2=4m1=2,m2=4(2)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0kx1=2,x2=5m1=5,m2=

14、6(3)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 17 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0kx1=1,x2=6m1=7,m2=11(4)Huffman树应用最佳判定树等级分数段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a90EYNDYNCYNBYNAHuffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长

15、最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例 要传输的字符集 D=C,A,S,T, ; 字符出现频率 w=2,4,2,3,3CS3364224814T;A00110110T : 00; : 01A : 10C : 110S : 111译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例 电文是CAS;CAT;SAT;AT 其编码 “110101110111010000111