数据结构与算法Data Structure.ppt

《数据结构与算法Data Structure.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法Data Structure.ppt（29页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构与算法Data Structure Algorithms烟台南山学院信息科技学院烟台南山学院信息科技学院烟台南山学院信息科技学院烟台南山学院信息科技学院数据结构与算法教学组数据结构与算法教学组数据结构与算法教学组数据结构与算法教学组16.4 树和森林1.树和森林与二叉树的转换树和森林与二叉树的转换2.树和森林的存储方式树和森林的存储方式3.树和森林的遍历树和森林的遍历21.树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1:step1:将树中同一结点的兄弟相连将树中同一结点的兄弟相连;step2:step2:保留结点的最左孩子连线，删除其它孩保留结点的最左孩子连

2、线，删除其它孩子连线；子连线；step3:step3:将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转4545度角。度角。加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？3方法：方法：加加线线抹线抹线旋转旋转 abeidfhgc树转二叉树举树转二叉树举例例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左根根根根结点肯定结点肯定结点肯定结点肯定没有右孩子！没有右孩子！没有右孩子！没有右孩子！4讨论讨论2 2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：把所有右孩子变为兄弟！要点：把所有右孩子变为兄弟！abeidfhg

3、c5法一：法一：各森林先各自转为二叉树；各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17，两种方法都有转换示意图），两种方法都有转换示意图）即即F=TF=T1 1,T,T2 2,T,Tm m B=root,LB,RB B=root,LB,RB6ABCDEFGHJIABCDEFGHJIA ABCDEFGHJI森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连

4、长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 A A7讨论讨论4 4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root,LB,RB F=TB=root,LB,RB F=T1 1,T,T2 2,T,Tm m 82.2.树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用双亲表示法来存储、用双亲表示法来存储思路：

5、思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示其双亲结点在链表中的位置。位置。parentsdata结点结构结点结构dataparents1树结构树结构 23n9A AB BC CGGE EI ID DHHF F缺点：求结点的孩子时需要遍历整个结构。缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例例1:双亲表示法双亲表示法10思路：将每个结点的孩子排列起来，形成一个带表头思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表

6、（装父结点）的线性表（n n个结点要设立个结点要设立n n个链表）；个链表）；再将再将n n个表头用数组存放起来，这样就形成一个混合个表头用数组存放起来，这样就形成一个混合结构。结构。例如例如：abecdfhgdefghgfedcbah123456782 2、用孩子表示法来存储、用孩子表示法来存储bc11思路：思路：用二叉链表来表示树，但链表中的两个用二叉链表来表示树，但链表中的两个指针域含义不同。指针域含义不同。左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3

7、3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟12abecdfhgbacedfgh问：问：树树转转二叉树的二叉树的“连线连线抹线抹线旋转旋转”如如何由计算机自动实现？何由计算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。存储的过程就是转换的过程！存储的过程就是转换的过程！例如例如：13先序遍历先序遍历F若森林为空，返回；若森林为空，返回；F访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；F先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；F先序遍历除去第一棵树之后剩余的树构成的森

8、林。先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历中序遍历F若森林为空，返回；若森林为空，返回；F中序遍历森林中第一棵树的根结点的子树森林；中序遍历森林中第一棵树的根结点的子树森林；F访问第一棵树的根结点；访问第一棵树的根结点；F中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历森林的遍历ABCDEFGHJI14路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：6.5 Huffman6.5 Huffman树及其应用树及其应用一、最优二叉树（一、最优二叉

9、树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 2101015HuffmanHuffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？WPLWPL=w wk kl

10、lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：经典之例：经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：哈夫曼树则是：WPL WPL 最小的树。最小的树。Huffman树树Weighted Path LengthWeighted Path Length16(1)(1)由给定的由给定的由给定的由给定的 n n 个权值个权值个权值个权值 w w0 0,w w1 1,w w2 2,w wn n-1-1，构造具有构造具有构造具有构造具有 n n 棵扩充棵扩充棵扩充棵扩充二叉树的二叉树的二叉树的二叉树的森林森林森林森林F F

11、=T T0 0,T T1 1,T T2 2,T Tn n-1-1 ，其中每一棵扩充二叉其中每一棵扩充二叉其中每一棵扩充二叉其中每一棵扩充二叉树树树树 T Ti i 只有一个带有权值只有一个带有权值只有一个带有权值只有一个带有权值 w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。(2)(2)重复以下步骤重复以下步骤重复以下步骤重复以下步骤,直到直到直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：在在在在 F F 中中中中选取两棵根结点的权值最小选取两棵根结点的权

12、值最小选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树的扩充二叉树的扩充二叉树,做为左、做为左、做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为根结点的权值为根结点的权值为根结点的权值为其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和。在在在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树

13、加入把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径。先先举例！举例！17例例1：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为出现的频度分别为7,5,2,7,5,2,4 4，怎样编码才能使它们组成的报文在网络中传得最快，怎样编码才能使它们组成的报文在网络中传

14、得最快？法法1 1：等长编码等长编码。例如用二进制编码来实现。例如用二进制编码来实现。取取 d=d=0000，i=i=0101，a=a=1010，n=n=1111怎样实现怎样实现HuffmanHuffman编码？编码？法法2 2：不等长编码不等长编码，例如用哈夫曼编码来实现。，例如用哈夫曼编码来实现。取取 d=d=0 0;i=;i=1010,a=,a=110110,n=,n=111111最快的编码是哪个？最快的编码是哪个？是非等长的是非等长的HuffmanHuffman码！码！先要构造先要构造HuffmanHuffman树！树！18操作要点操作要点1 1：对权值的合并、删除与替换对权值的合并、

15、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：方框表示外结点（叶子，字符对应的权值注：方框表示外结点（叶子，字符对应的权值），），圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。19操作要点操作要点2 2：按左按左0 0右右1 1对对HuffmanHuffman树的所有分支编号！树的所有分支编号！d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0,i=,i=1010,a=,a=

16、110110,n=,n=111111WPL=1bitWPL=1bit7 72bit2bit5+3bit(2+4)=5+3bit(2+4)=3535特点：每一码都不是另一码的前缀，绝不会错译特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码称为前缀码将将将将 HuffmanHuffman树树 与与 HuffmanHuffman编码编码 挂钩挂钩20例例2 2（严题集（严题集6.266.26）：假设用于通信的电文仅由假设用于通信的电文仅由8 8个字母个字母 a,b,c,d,e,f,g,ha,b,c,d,e,f,g,h 构成，它们在电文中出现的概率分构成，它们在电文中出现的概率分别为别为 0.0

17、7,0.19,0.02,0.06,0.32,0.03,0.21,0.10 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这试为这8 8个字母设计哈夫曼个字母设计哈夫曼编码。编码。如果用如果用0 07 7的二进制编码方案的二进制编码方案又如何？又如何？霍夫曼霍夫曼编码的基本思想是：编码的基本思想是：概率大的字符用短码，概率小的用概率大的字符用短码，概率小的用长码。由于长码。由于霍夫曼树的霍夫曼树的WPLWPL最小，最小，说明编码所需要的比特数最说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。少。这种编码已广泛应用于网络通信中。解：解：先将概率放大

18、先将概率放大100100倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。权值集合权值集合 w=7,19,2,6,32,3,21,10w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。21w4=19,21,w4=19,21,28,28,32 32为清晰起见，重新排序为为清晰起见，重新排序为:w=2,3,6,7,10,19,21,32w=2,3,6,7,10,19,21,322 23 35 56 6w1=w1=5,5,6,7,10,19,21,32 6,7,10,19,21,32w2=7,10

19、,w2=7,10,11,11,19,21,32 19,21,32w3=w3=11,17,11,17,19,21,32 19,21,32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼树哈夫曼树 22对应的哈夫曼编码（左对应的哈夫曼编码（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc ca ad de e

20、g gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 110011000000111101

21、11101110111010101111111111010111011101000001010011100101110111二进制码二进制码二进制码二进制码23另一种结果表示：另一种结果表示：24例例3 3（实验二方案（实验二方案3 3）：设字符集为设字符集为2626个英文字母，其出个英文字母，其出现频度如下表所示。现频度如下表所示。注：若圆满实现了此方案，平时成绩将以满分计。注：若圆满实现了此方案，平时成绩将以满分计。51481156357203251频度频度zyxwvut t字符字符11611882380频度频度p21fq15gr47hsonmlkj字符字符5710332221364186

22、频度频度ie edcba空格空格空格空格字符字符先建哈夫曼树，再利用此树对报文先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。进行编码和译码。要求编程实现：要求编程实现：25提示提示1 1：霍夫曼树中各结点的结构霍夫曼树中各结点的结构可以定义为如下可以定义为如下5 5个分量：个分量：charweight parentlchildRchild将整个将整个霍夫曼树的霍夫曼树的结点结点存储在一个数组中：存储在一个数组中：HT1.n;HT1.n;将结点的将结点的编码编码存储在存储在HC1.nHC1.n中。中。提示提示3 3：霍夫曼树如何构造？霍夫

23、曼树如何构造？构造好之后又如何求得构造好之后又如何求得各结点对应的霍夫曼编码？各结点对应的霍夫曼编码？算法参见教材算法参见教材P147P147。提示提示2 2：霍夫曼树的霍夫曼树的存储结构存储结构可采用可采用顺序存储顺序存储结构：结构：实验二补充材料中的方案二程序；实验二补充材料中的方案二程序；喻信星空喻信星空FTPFTP网站上的网站上的“数据结构数据结构”演示程序演示程序参考参考参考参考资料资料资料资料26二叉树小结1 1、定义和性质、定义和性质2 2、存储结构、存储结构3 3、遍历、遍历4 4、线索化、线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先

24、序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树二叉树二叉树森林中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码27void iter_inorder(tree_pointer node)int top=-1;/*initialize stack*/tree_pointer stackMAX_STACK_SIZE;for(;)for(;node;node=node-left_child)add(&top,node);/*add to stack*/node=delete(&top);/*delete from stack*/if(!node)br

25、eak;/*empty stack*/printf(“%D”,node-data);node=node-right_child;时间复杂度时间复杂度O(n)附：中序遍历迭代算法附：中序遍历迭代算法(利用堆栈利用堆栈)28void level_order(tree_pointer ptr)/*level order tree traversal*/int front=rear=0;tree_pointer queueMAX_QUEUE_SIZE;if(!ptr)return;/*empty queue*/addq(front,&rear,ptr);for(;)ptr=deleteq(&front,rear);+*E*D/C A B附：层序遍历算法附：层序遍历算法(利用队列利用队列)29