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

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

2、其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子l二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树例 10，18，3，8，12，2，7，310101810183101838101838 12101838 122101838 1227101838 12273中序遍历二叉排序树可得到一个关键字的有序序列v查找树的删除要删除查找树中的p结点，分三种情况：lp为叶子结点，只需修改p双亲f的指针f-lchild=NULL f-rchild=NULLlp只有左子树或右子树up只有左子树，用p的左孩子代替p (1)(2)u

3、p只有右子树，用p的右孩子代替p (3)(4)lp左、右子树均非空u沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p (5)u若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中

4、序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：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 满树、拟满树和丰满树定义v满树：每层结点数达到最大个数v拟满树：深度为k的二叉树，

5、前k-1层是满树，第k层从左到右依次排列v丰满树：深度为k的二叉树，前k-1层是满树，第k层任意排列6.3 堆和堆排序v堆的定义：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个元素的最小值或最大值v堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n

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

7、849502765769713输出：13 276549502738769713输出：13 27 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

8、38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97v第一个问题解决方法l方法：构造一棵拟满树，从最后一个根开始调整成堆结构，直至到根例 含8个元素的无序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650976.4 平衡树定义v树的高度 设T是一棵二叉树,h(T)表示树T的高度.则 h(T)=maxh(Tl,Tr)+1v平衡度(k)=h(Tkr)-h(Tkl)v平衡树 二叉树中

9、每个结点k都有|(k)=|1v平衡查找树 树T既是查找树,又是平衡树 1、按查找树插入2、调整LL型 新结点插入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的顺序

10、构造一棵平衡查找树G0G-1F0G-2F-1A0A1F-1D0G0F0A0G0A2F-2D-1G0C0F-1C0G0A0D0例：按G,F,A,D,C,E,B的顺序构造一棵平衡查找树F-2C1G0A0D1E0D0C-1A0F0E0 G0D-1C-2A1F0E0 G0B0C0A0B0F0E0G0D06.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、树v定义l路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的l路径长度：路径上的分支数l树的路径长度：从树根到每一个结点的路径长度之和l树的带权路径长度：树中所有带权结点的路径长度之和结点到根的路径长度权值其中：记作：kknkkklwlwwpl1lHuffman树设有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+

12、5*2+2*3+4*3=35nkKKLWWPL1v构造Huffman树的方法Huffman算法v构造Huffman树步骤l根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wjl在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和l在森林中删除这两棵树，同时将新得到的二叉树加入森林中l重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1

13、135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100lc 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,

14、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=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)vHuffman树应用l最佳判定树等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYN

15、CYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a90EYNDYNCYNBYNAlHuffman编码：数据通信用的二进制编码u思想：根据字符出现频率编码，使电文总长最短u编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例 要传输的字符集 D=C,A,S,T,;字符出现频率 w=2,4,2,3,3CS3364224814T;A00110110T:00;:01A:10C:110S:111u译码：从Huffman树根开始，从

16、待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例 电文是CAS;CAT;SAT;AT 其编码 “11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111m26.7 B-树B-树是一种平衡的多叉树，一棵m阶B-树具备下列性质：1、每个结点的子结点个数m2、除根和叶子之外，每个结点的子结点个数3、根结点至少有两个子结点，除非它同时又是叶子，此时它没有子结点4、所有叶子都出现在同一层上，而且不带有信息5、具有k个子结点的非叶子结点含有k-1个键值