数据结构与算法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 中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法Data Structure 数据结构 算法 Data
限制150内