《树与森林转换》PPT课件.ppt

《《树与森林转换》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、双亲表示法二、孩子表示法三、树的二叉链表(孩子-兄弟）存储表示法6.4树和森林树的三种存储结构ACBDEFGdataparent一、双亲表示法利用每个非根结点有一个双亲的性质,在每个结点附设指示器指示其双亲所在位置。r0A-11B02C03D04E25F26G5如何找双亲、孩子结点特点：找双亲容易，找孩子难二、孩子表示法:每个结点有多个指针域，其中每个指针指向一棵子树根结点。结点有两种方式：a)链表中结点同构，链表中域的数目为树的度；b)非固定大小结点结构。1、多重链表表示法：datachlid1child2········

2、····cihldd树的度结点的度datadegreechild1child2···········childd若结点采用格式a)表示，则空间可能会较浪费；若结点采用格式b)表示，则操作较为不便。ACBDEFG0A1B2C3D4E5F6Gr2、孩子链表表示法：把树的每个结点的孩子排列起来，看成一个线性表，且以单链表作存储结构。则n个结点的树就有n个孩子链表；r=0,n=7123456-1000225并将n个头指针也看成一个线性表，采用顺序存储结构。孩子链表便于涉及孩子的操作的实现，却不适用于涉及双亲的操作，可将其和双亲表示结合在

3、一起。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。三、二叉链表(孩子-兄弟）表示法firstchilddatanextsibling结点结构:typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;ACBDEFGrootrootABCEDFGrootABCEGDFCDFABEGroot此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表表示IACBDHGFE(a)AIHDGFCEB

4、(b)FIABDHGCE树与二叉树的对应关系森林与二叉树的转换一、树转化为二叉树以二叉链表为媒介可导出树与二叉树之间的一个对应关系。即给定一棵树，可以找到唯一的一棵二叉树与之对应。用一棵二叉树表示一棵树，可以很好地解决树的存储表示问题，而且树的各种操作均可对应二叉树的操作来完成。转换方法：1、(连兄弟)在树中个兄弟之间加一连线；2、(断父子)对于任一结点，只保留它与最左孩子之间的连线；3、(转一转)分别以每个结点的第一个孩子结点为轴心，将其右边兄弟结点顺时针转45°ACBDEFG连兄弟断父子转一转ABCEDFG说明：由树转换成的

5、二叉树，其根结点的右子树总是空的。二叉树的根结点即是对应树的根结点，二叉树中任何结点与其左孩子是树中双亲孩子关系，而与其右孩子则是对应树中的兄弟关系。由此我们也可方便地将右子树为空的二叉树转化为树。二、二叉树转化为树转换方法：1、(连祖孙)将结点与其左孩子的右子孙连接；2、(断父子)对于任一结点，只保留它与左孩子之间的连线；3、(抖一抖)将结点按层次排列，形成树结构。ABCEDFGACBDEFG三、森林转化为二叉树转换方法：将森林中的每一棵树依次转换成相应的二叉树;将第二棵作为第一棵二叉树的根结点的右子树连接起来，将第三棵又作为

6、第二棵的右子树连接起来......直至把所有的二叉树连接成一棵二叉树。ACBDEFGKLHIJABECDFGHIJKL四、二叉树转化为森林将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树;转换方法：将森林中的每一棵二叉树依次转换成树。ACBDEFGKLHIJABECDFGHIJKL练习：1、将二叉树转换为森林。ABEDCFGHIJ2、将森林转换为二叉树。12AHIKJCDEFG树的遍历森林的遍历树和森林的遍历按层次遍历:先根(序)遍历:后根(序)遍历:若树不空，则先访问根结点，然后

7、依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。树的遍历有三条搜索路径先根序列：ABEFCDGHIJK后根序列：EFBCIJKHGDA层次序列：ABCDEFGHIJKACBDFEGHIJK一棵树的三种遍历序列1)森林中第一棵树的根结点；2)森林中第一棵树的子树森林；3)森林中其它树构成的森林。森林由三部分构成：CDGKLMMBFEHIJ1.先序遍历：若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林;先序遍历森林中(除第一棵树之外)其

8、余树构成的森林。即依次从左至右对森林中的每一棵树进行先根遍历。森林的遍历即依次从左至右对森林中的每一棵树进行后根遍历。2.中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林。先序