第13讲 树与哈夫曼编码ppt课件.ppt

《第13讲 树与哈夫曼编码ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13讲树与哈夫曼编码主讲人：陈红丽树的存储结构实现树的存储结构，关键是什么?如何表示树中结点之间的逻辑关系。思考问题的出发点如何表示结点的双亲和孩子双亲表示法孩子表示法双亲孩子表示法孩子兄弟表示法使用一组地址连续的空间（数组）存储树的结点，同时在每个结点中附设一个指示器来指示其双亲结点的位置。即：每个数组元素包含两个域：数据域：存放结点本身的信息。双亲域：指示该结点的双亲结点在数组中的位置双亲表示法#defineMAX_TREE_SIZE100//树的最大结点数typedefstructPTNode{//数组元素的结点结构TElemTypeweight;intpare

2、nt;}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];introot,nodenum;//根结点的位置和结点个数}PTree;树的双亲表示法举例ACDEFGHKB001136660R-16012345789weightparentCFKHGBRADE很容易查找到结点的双亲，但查找结点的孩子时要遍历整个结构。r=0,n=10孩子表示法首先使用数组来存放树的每个结点。每个数组元素有两个域：weight域和孩子指针域。树中每个结点的孩子使用单链表组织起来。该元素的孩子指针域指向孩子链表。如果没有孩子，则孩子指针域为空。type

3、defstructCTNode{//孩子结点intchild;structCTNode*next;}CTNode,*ChildPtr;typedefstruct{TElemTypeweight;ChildPtrfirstchild;//孩子链的头指针}CTBox;typedefstruct{//树CTBoxnodes[MAX_TREE_SIZE];intnodenum,root;//结点数和根结点的位置}CTree;CFKHGBRADE6012345789weightfcGHACDEFKBR1^234^5^^67^89^^^^^树的孩子表示法举例很容易查找到结点的孩子，

4、但查找结点的双亲时要遍历整个结构。r=0,n=10双亲孩子表示法6012345789weightfcGHACDEFKBR1^234^5^67^89^^^^^^660011360-1parentCFKHGBRADE孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和右边的下一个兄弟结点。typedefstructCSNode{ElemTypeweight;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;孩子兄弟表示法举例CFKHGBRADEADB∧E∧∧R∧GFC∧∧∧H∧K∧

5、∧A的右兄弟结点A的第一个孩子结点∧EHRACFGBDK1.加线ABCDEFG树和二叉树之间的转换2.保留双亲与第一孩子连线,删去与其他孩子的连线ABCDEFG3.顺时针转动,使之层次分明GDABECF特点是？根结点没有右孩子！兄弟相连长兄为父孩子靠左ABCDEFGHI练习题：请把图a的树转换成相应的二叉树。图a树ABCDEFGHI图b二叉树讨论：二叉树怎样还原为树？要点：逆操作，把所有右孩子变为兄弟！abeidfhgcabdefhgic森林和二叉树的转换森林转换成二叉树的方法：将每棵树分别转换成二叉树依次连到前一个二叉树的右子树上。ABCDEFGHIJABCDEFGH

6、IJABCDEFGHIJABCDEFGHIJ有3棵树的森林：（a）森林（b）每棵树对应的二叉树（c）连线（d）整理，最终二叉树抹线：将二叉树中根结点与其右孩子之间的连线，及沿右分支搜索到的所有右孩子间的连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。二叉树还原为森林要点：把最右边的子树变为森林，其余右子树变为兄弟。ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树有3棵树的森林抹线将二叉树还原为树练习题：请画出和下列二叉树对应的森林。EIJFBKADCGGEJIBKFADC树的遍历树的遍历先根、后根层次先根遍历访问根

7、结点；按照从左到右依次先根遍历根结点的每棵子树。后根遍历按照从左到右依次后根遍历根结点的每棵子树；访问根结点。树没有中序遍历（因子树不分左右）ACBGFEDHI先根遍历序列：ABDEHIFCG后根遍历序列：DHIEFBGCA树若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：decbaabdecabcdebdcea先根序列：后根序列：abcdebdcea1.树的先根遍历与二叉树的先序遍历相同；2.树的后根遍历相当于二叉树的中序遍历；3.树没有中序遍历，因为子树无左右之分。结论：先序遍历：后序遍历：中序遍历