算法与数据结构-树第6章3.pptVIP

6.5树和森林 树的存储结构 森林、树、二叉树之间的相互转换 树和森林的遍历 树的存储结构 双亲表示法 使用静态数组（本质是静态链表）； 数组的每个数据元素，包括两个域：一个域是数据元素；另一个域用游标指示该结点的双亲结点在数组中的相对位置；根结点的游标为-1。 特点： 方便找结点的双亲； 顺序存储结构； 双亲表示示例 双亲表示法存储结构定义 孩子表示法 任一数据元素，有0个或多个孩子； 因此可以设计一个链式存储结构，其结点除放置数据元素外，还放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中的位置。 孩子表示法 方法1 根据结点的度，设置结点的指针个数，比如若结点的度为m: 孩子表示法 方法2 按照树的度定义结点。若树的度为d,设置结点中有d个指针域，同时设置degree，表示该结点的度。 孩子表示法 有n个结点的树的度为k，空指针域有n(k-1)+1个。 证明： n个结点的树，除根结点外，每个结点有一个指针指向，也就是树中有n-1个有效链域（指针） 而按该结点定义，n个结点总的指针域有：nk个。 因此空链域： nk – (n-1) = n ( k - 1 ) + 1 方法3 每个结点的孩子排列起来形成一个链表； 所有链表的头结点放在一个静态数组中； 数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表， 链表结点的数据域是一个整数，表示该结点的孩子在数组中的相对位置； 孩子表示法 孩子表示法存储结构定义 特点： 顺序+链式存储结构； 找孩子容易，找双亲难； 双亲孩子链表 在静态数组的结点中增加一个域，表示该结点的双亲在该数组中的相对位置。 有利于寻找孩子结点和双亲结点。 孩子兄弟表示法 又称二叉树表示法，用二叉链表作为树的存储结构。 链表结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点 从向下的纵向和向右的横向描述树； 孩子兄弟表示法 typedef struct CSNode {ElemType data; struct CSNode *firstchild, *nextsibling; }CSNode,*CSTree; 孩子兄弟表示法 树的存储结构： 双亲表示法----静态链表 孩子表示方法----多重链表 双亲孩子法 ----顺序+链式结构 孩子兄弟表示方法----二叉链表 树和二叉树的转化 若树采用孩子兄弟表示法，二叉树采用二叉链表表示，在使用该存储结构下，树和二叉树是等价的，树可以转化为二叉树。 树和二叉树转化例 任一棵树，都可以找到唯一的一棵二叉树和它对应， 而且该二叉树没有右子树， 因此一棵二叉树，不一定保证能转换为一棵树 森林到二叉树的转换 若树采用孩子兄弟表示法，二叉树采用二叉链表表示，则： 把森林的第一棵树的根节点看作是转换后二叉树的根结点，把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树。 依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则 森林到二叉树的转换 步骤： （1）连线：在兄弟（各树的根结点看作兄弟）结点之间加一条连线。 （2）切线：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线。 （3）旋转：将按（1）、（2）的方法形成的二叉树，沿顺时针方向旋转450,就可以得到一棵形式上更为清楚的二叉树。 二叉树到森林的转换 如果B={root,LBT,RBT}是一棵二叉树，F={T1 ,T2 ,…,Tn}表示与其对应的森林，转换规则如下： （1）若B为空，则F为空； （2）若B非空，则F中第一棵树T1的根即为二叉树B的根root，T1中根结点的子树森林F1是由B的左子树LBT转换而成的森林；F中除T1之外其余树组成的森林F’={ T2 ,T3…,Tn}是由B的右子树RBT转化而成的森林。 具体做法： 若二叉树某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子，……都和该结点的双亲用线连接起来，最后去掉所有的双亲到右孩子的连线。 二叉树到森林的转换例1 树和森林的遍历 树的遍历 树的遍历与二叉树遍历对应 森林的遍历 森林的遍历与二叉树的遍历对应 树的前序遍历序列与其对应的二叉树的前序遍历序列相同； 树的后序遍历序列与其对应的二叉树的中序遍历序列相同； C H A B G D F E C G H A B D F E 前序遍历：ABEFCDGH 后序遍历：EFBCGHDA 前序遍历： ABEFCDGH 中序遍历： EFBCGHDA * * A B E C D F 双亲表示法 孩子表示法 孩子兄弟表示法