4.树、森林

树的存储结构

1.双亲表示法

image.png

可以很快地得到每个结点的双亲结点,但求结点的孩子时则需要遍历整个结构

2.孩子表示法

image.png

这种存储结构寻找子女的操作非常直接,而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

3.孩子兄弟表示法

最大的优点是可以方便地实现树转换为二叉树的操作

image.png

树、森林与二叉树的转换

每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟,这个规则又称 “左孩子右兄弟”

image.png

image.png

提示

结论:设F是一个森林，B是由F变换来的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有$n+1$个。
证明:根据森林与二叉树转换规则“左孩子右兄弟”。二叉树 B 中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，故树B中右指针域为空的结点有n+1个。

树的遍历

图5.16的树的先根遍历序列为 ABEFCDG,后根遍历序列为EFBCGDA

先根遍历

• 先根后子树
• 其遍历序列与这棵树相应二叉树的先序序列相同

后根遍历

• 先子树后根的规则
• 其遍历序列与这棵树相应二叉树的中序序列相同

后根遍历树可分为两步:

1. 从左到右访问双亲结点的每个孩子(转化为二叉树后就是先访问根结点再访问右子树);
2. 访问完所有孩子后再访问它们的双亲结点(转化为二叉树后就是先访问左子树再访问根结点)
3. 因此树的后根遍历序列与其相应二叉树的中序遍历序列相同

树T转换为二叉树 BT 的过程如下图所示,树T的后序遍历序列显然和其相应二叉树 BT 的中序遍历序列相同,均为 5,6,7, 2,3,4,1。

image.png

森林的遍历

图5.17 的森林的先序遍历序列为ABCDEFGHI,中序遍历序列为BCDAFEHIG.

先序遍历森林

若森林为非空,则按如下规则进行遍历:

1. 访问森林中第一棵树的根结点。
2. 先序遍历第一棵树中根结点的子树森林。
3. 先序遍历除去第一棵树之后剩余构成的森林

中序遍历森林

森林为非空时,按如下规则进行遍历：

1. 中序遍历森林中第一棵树的根结点的子树森林。
2. 访问第一棵树的根结点。
3. 中序遍历除去第一棵树之后剩余的树构成的森林。

注意

部分教材也将森林的中序遍历称为后序遍历,称中序遍历是相对其二叉树而言的,称后序遍历是因为根确实是最后才访问的,如遇到这两种称谓,那么都可以理解为同一种遍历方法。