树与森林转换.pptVIP

* * * * * * * * * * * * * * * * * * * * * 一、双亲表示法 二、孩子表示法 三、树的二叉链表(孩子-兄弟） 存储表示法 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 ············ cihldd 树的度 结点的度 data degree child1 child2 ··········· childd 若结点采用格式?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 D E 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