信管第六章 树和二叉树.ppt

2、孩子表示法（链式存储结构） 为了方便地找到某个结点的孩子结点，可以采用孩子表示法来存储树结构。因为树中每个结点可能会有多棵子树，因此用多重链表表示树结构。 a) 结点采用同一种结构（结点同构） 其中d是树的度，也就是树中结点度数的最大值。 树中很多结点的度小于d，因此会有很多空链域，造成存储空间的浪费，但易于管理。 b) 结点不采用同一种结构（结点不同构） 其中d是该结点的度数，degree的值同d的值相同。 这种存储结构虽然能节省存储空间，但由于结点不同构，所以在管理上有一定难度。 c) 建立孩子链表 另一种方法是把每个结点的孩子结点排列起来，看成是一个线性表，而且以单链表作存储结构，因此n个结点就有n个孩子链表，n个头指针又组成一个顺序表，采用顺序存储结构。 上述结构可以很方便地找到某个结点的孩子结点，但是不适用于找某结点的双亲，因此可以把双亲表示法和孩子表示法结合起来，形成带双亲的孩子链表。 3、孩子兄弟表示法 在树的各种存储结构中，最常用的是孩子兄弟表示法，又称二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构，链表中的结点的两个指针域分别指向该结点的第一个孩子结点和它的下一个兄弟结点。 类型说明： //—树的二叉链表（孩子—兄弟）存储表示—// typedef struct CSNode { ElemType data； struct CSNode *firstchild,*nextsibling； }CSNode,*CSTree； 说明： 在这种存储结构中可以很方便地实现各种树的操作。 如：易于实现找结点孩子等的操作。若要访问结点x的第i个孩子，则只要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，便可以找到x的第i个孩子。 树的二叉链表表示法与二叉树的二叉链表表示法虽然形式不同，但是在计算机内的存储表示是唯一对应的，如下图所示： 值得注意的问题： 存储如下所示：按列方向存储的是 结论： 树和二叉树的物理存储结构相同，但解释不同，即指针域的含义不同，由此可见，一棵树可唯一确定地转换成二叉树。也就是说，以二叉链表作为媒介，可以导出树与二叉树之间的确定对应关系。 在树的孩子兄弟表示法中，由于树的根结点没有兄弟结点，所以树的根结点的右指针域为空，对应到二叉树中就是二叉树的根结点的右子树为空。 6.5.2 森林与二叉树的转换 从树的二叉链表表示可知，任何一棵和树对应的二叉树，其右子树必为空。 若把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则同样可以导出森林和二叉树的对应关系。 1、森林转换成二叉树 将森林转换为二叉树的一般步骤为： (1)若森林为空，则为空的二叉树。 (2)若森林不为空将森林中每棵子树转换成相应的二叉树，按照兄弟孩子法转换。形成有若干二叉树的森林，如图 (ｂ)所示。 (3) 将第一棵树的根作为转换后二叉树的根，第一棵树的左子树作为转换后的二叉树的左子树，第二棵树作为转换后的二叉树的右子树图(c)，第三棵树作为转换后的二叉树右子树的右子树，依次类推，即将其余的树都连接在二叉树的右分支上。图是将一个森林转化为一棵二叉树的示例。图(d)是转化后的一棵二叉树。 A B C D F E H G I J (b) J I H G D F E C B A (c) A B E G F C D H I J (d) F E (a) C B D A H G I J 图 森林转换为二叉树 一般树的森林；(b) 二叉树的森林； (c) 第二棵子树并入第一棵子树；(d) 最终结果 2. 二叉树还原为森林 将一棵由森林转换得到的二叉树还原为森林，其步骤是： (1)抹线：将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森林。 (2)还原：将每棵二叉树按二叉树还原一般树的方法还原为一般树，于是得到森林。 例如：下图将AE之间的线去掉，EG之间的线去掉，保留双亲和第一个子女的连线。该例转换为三个二叉树，然后再将二叉树转化为树即可,也是按照孩子兄弟法转换。 A B C D F E H G I J (b) A B E C D F G H I J (a) F E C B D A H G I J (c) 6.5.3 一般树或森林的遍历 1. 一般树的遍历 在树和森林中，一个结点可能有两棵以上的子树，因此不便讨论它们的中序遍历，可见树的遍历只能有先根次序和