第327章 半(第2页)

◆从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。

2、二叉树转换成树

对于一棵转换后的二叉树，如何还原成原来的树?其步骤是：

（1）加虚线。若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右

子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连，

如图(a)所示。

（2）去连线。去掉二叉树中所有父结点与其右子结点之间的连线，如图(b)所示。

（3）规整化。将图中各结点按层次排列且将所有的虚线变成实线，如图(c)所示。

3、森林转换成二叉树

转换步骤：

1将f={t1,t2,?,tn}中的每棵树转换成二叉树。

2按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的

根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，如图

所示。

4、二叉树转换成森林
上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。

1去连线。将二叉树b的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连

线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林f中的树依次对应的二叉树。2二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树。

5、树的遍历

由树结构的定义可知，树的遍历有二种方法。

(1)先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图，先序遍历的次序是：

Abcdefgijhk

(2)后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图，后序遍历的次序是：

cdbfijghekA

树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。

树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同

【2019年】若将一棵树t转化为对应的二叉树bt，则下列对bt的遍历中，其遍历序列

与t的后根遍历序列相同的是（）

A.先序遍历b.中序遍历c.后序遍历d.按层遍历

【2020年】已知森林f及与之对应的二叉树t，若f的先根遍历序列是a,b,c,d,e,f，中