树与森林转换.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一、双亲表示法,二、孩子表示法,三、树的二叉链表,(,孩子,-,兄弟）,存储表示法,6.4,树和森林,树的三种存储结构,A,C,B,D,E,F,G,data parent,一、,双亲表示法,利用每个非根结点有一个,双亲的性质,在,每个结点附设指示器指示其,双亲所在位置,。,r,0,A,-1,1,B,0,2,C,0,3,D,0,4,E,2,5,F,2,6,G,5,如何找双亲、孩子结点,特点：,找双亲容易，找孩子难,二、孩子表示法,:,每个结点有多个指针域，其中每个指针指向一棵子树根结点。,结点有两种方式：,a),链表中结点同构，链表中域的数目为树的度；,b),非固定大小结点结构。,1,、多重链表表示法：,data,chlid1 child2,cihld,d,树,的度,结点,的度,data,degree,child1 child2,child,d,若结点采用格式,a),表示，则,空间,可能会较,浪费,；,若结点采用格式,b),表示，则,操作,较为,不便,。,A,C,B,D,E,F,G,0,A,1,B,2,C,3,D,4,E,5,F,6,G,r,2,、孩子链表表示法：,把树的每个结点的孩子排列起来，看成一个线性表，且以单链表作存储结构。则,n,个结点的树就有,n,个孩子链表；,r=,0,n=,7,1 2 3,4 5,6,-1,0,0,0,2,2,5,并将,n,个头指针也看,成一个线性表，采用顺序存储结构。,孩子链表,便于涉及,孩子的操作的实现，却不适用于,涉及,双亲的操作，可将其和双亲表示结合在一起。,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。,三、二叉链表,(,孩子,-,兄弟）表示法,firstchild,data,nextsibling,结点结构,:,typedef,struct,CSNode,ElemType,data;,struct,CSNode,*,firstchild,*,nextsibling,;,CSNode,*,CSTree,;,A,C,B,DE,F,G,root,root,A,B,C,E D,F,G,root,A,B,C,E,G,D,F,C,D,F,A,B,E,G,root,此二叉链表既是树,(a),的孩子,兄弟表示又是二叉树,(b),的二叉链表表示,I,A,C,B,D,H,G,F,E,(a),A,I,H,D,G,F,C,E,B,(b),F,I,A,B,D,H,G,C,E,树与二叉树的对应关系,森林与二叉树的转换,一、树,转化为,二叉树,以二叉链表为媒介可导出树与二叉树之间的一个对应关系。即给定一棵树，可以找到唯一的一棵二叉树与之对应。用一棵二叉树表示一棵树，可以很好地解决树的存储表示问题，而且树的各种操作均可对应二叉树的操作来完成。,转换方法：,1,、,(,连兄弟,),在树中个兄弟之间加一连线；,2,、,(,断父子,),对于任一结点，只保留它与最左孩,子之间的连线；,3,、,(,转一转,),分别以每个结点的第一个孩子结点为轴,心，将其右边兄弟结点顺时针转,45,A,C,B,D,E,F,G,连兄弟,断父子,转一转,A,B,C,E D,F,G,说明：,由树转换成的二叉树，其根结点的右子树总是空的。,二叉树的根结点即是对应树的根结点，,二叉树中任何结点与其左孩子是树中双亲孩子关系，,而与其右孩子则是对应树中的兄弟关系。,由此我们也可方便地将右子树为空的二叉树转化为树。,二、二叉树,转化为,树,转换方法：,1,、,(,连祖孙,),将结点与其左孩子的右子孙连接；,2,、,(,断父子,),对于任一结点，只保留它与左孩子,之间的连线；,3,、,(,抖一抖,),将结点按层次排列，形成树结构。,A,B,C,E D,F,G,A,C,B,D,E,F,G,三、森林,转化为,二叉树,转换方法：,将森林中的每一棵树依次转换成相应的二叉树,;,将第二棵作为第一棵二叉树的根结点的右子树连接起来，将第三棵又作为第二棵的右子树连接起来,.,直至把所有的二叉树连接成一棵二叉树。,A,C,B,D,E,F,G,K,L,H,I,J,A,B,E,C,D,F,G,H,I,J,K,L,四、二叉树转化为森林,将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树,;,转换方法：,将森林中的每一棵二叉树依次转换成树。,A,C,B,D,E,F,G,K,L,H,I,J,A,B,E,C,D,F,G,H,I,J,K,L,练习：,1,、将二叉树转换为森林。,A,B,E,D,C,F,G,H,I,J,2,、将森林转换为二叉树。,1,2,A,H,I,K,J,C,D,E,F,G,树的遍历,森林的遍历,树和森林的遍历,按层次遍历,:,先根,(,序,),遍历,:,后根,(,序,),遍历,:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,树 的 遍 历,有三条搜索路径,先根序列：,A B E F C D G H I J K,后根序列：,E F B C I J K H G D A,层次序列：,A B C D E F G H I J K,A,C,B,D,F,E,G,H,I,J,K,一棵树的三种遍历序列,1,),森林中第一棵树的根结点；,2,),森林中第一棵树的子树森林；,3),森林中其它树构成的森林。,森林由三部分构成：,C,D,G,K,L,M,M,B,F,E,H,I,J,1.,先序遍历,：,若森林不空，则,访问森林中第一棵树的根结点,;,先序遍历森林中第一棵树的子树森林,;,先序遍历森林中,(,除第一棵树之外),其,余树构成的森林。,即依次从左至右对森林中的每一棵树进行先根遍历。,森 林 的 遍 历,即,依次从左至右,对森林中的每一棵,树,进行,后根遍历,。,2.,中序遍历：,若森林不空，则,中序遍历森林中第一棵树的子树森林,;,访问森林中第一棵树的根结点,;,中序遍历森林中,(,除第一棵树之外,),其,余树构成的森林。,先序序列为,ABCDEFGHIJ,中序序列为,BCDAFEHJIG,先序序列为,ABCDEFGHIJ,中序序列为,BCDAFEHJIG,A,E,F,G,J,I,H,D,C,B,二叉树表示的森林,A,B,C,D,E,F,G,H,I,J,树与森林的遍历和二叉树的遍历的对应关系,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,树的先根序遍历与后根序遍历可通过对其相应的二叉树的进行先序遍历和中序遍历得到,。,赫,夫曼树及其应用,一、最优树,(,赫夫曼树,),的概念,非完全二叉树,a,b,c,f,d,e,g,h,结点的路径长度：,从根到该结点的路径长度；,树的路径长度：,树中所有结点的路径长度之和；在结点数相同的条件下，完全二叉树是路径长度最短的二叉树。,完全二叉树,a,b,c,g,d,e,h,f,PL=14,PL=13,结点的权：,根据应用需要给树的结点赋予的一个有意义的数值量；,7,5,2,4,d,a,b,c,7,5,c,d,b,a,2,4,5,a,2,b,c,d,7,4,WPL=36,WPL=46,WPL=35,结点的带权路径长度：,该结点的路径长度与权的乘积；,树的带权路径长度,=,树中所有叶子结点的带权路径之和；通常记作,WPL=,w,i,l,i,赫夫曼树：,假设有,n,个权值,(w,1,w,2,w,n,),，构造有,n,个叶子结点的二叉树，每个叶子结点带权为,w,i,，则其中带权路径长度,WPL,最小的二叉树称为,赫夫曼树。,赫夫曼树的特点：,权值越大的叶子结点越靠近根结点，,而权值越小的叶子结点越远离根结点。,2.,只有度为,0,（叶子结点）和度为,2,（分,支结点）的结点，不存在度为,1,的结点,.,15,40,30,5,10,1,根据给定的,n,个权值，构造,n,棵只有一个根结点 的二叉树，,n,个权值分别是这些树根结点的权。设森林,F,是由这,n,棵树构成的集合；,(,原始森林,),二,、赫夫曼树的构造,2,在,F,中选取两棵根的权值最小的树作为左、右子,树，构造一棵新二叉树，置新二叉树根的权值,=,左、右子树根结点权值之和；,(,每次新增一个结点,),3,从,F,中删除这两棵树,并将新树加入,F,;,(,每次少一棵树,),4,重复,2,、,3,，直到,F,中只含一颗树为止,;,(,要重复,n-1,次,),步骤：,例：构造以,W=,（,5,，,15,，,40,，,30,，,10,）为权的赫夫曼树。,155,10,15,5,10,15,30,30,5,10,15,5,10,15,30,15,60,60,5,5,5,10,15,30,15,5,10,15,30,15,60,30,100,最优二叉树的构造,26,构造以,W=(3,4,2,3,1),为权的最优二叉树。,a,3,b,4,c,2,d,3,e,1,3,6,7,13,Huffman,树不唯一,.,练习,w=5,29,7,8,14,23,3,11,试以它们为叶子结点构造一棵,Huffman,树，并计算带权路径长度,.,5,14,29,7,8,23,3,11,14,29,7,8,23,11,3,5,8,8,7,15,14,29,23,3,5,8,11,11,3,5,8,19,14,29,23,8,7,15,11,3,5,8,19,29,23,14,8,7,15,29,29,14,8,7,15,29,11,3,5,8,19,23,42,11,3,5,8,19,23,42,29,14,8,7,15,29,58,11,3,5,8,19,23,42,29,14,8,7,15,29,58,100,WPL=,？,271,