二叉树遍历方法
1.中序遍历的投影法
如果给定一棵二叉树的图形形态，是否能根据此图快速地得出其中序遍历的序列？回答是肯定的。

具体做法是：首先按照二叉树的标准绘制二叉树形态，即将所有左子树都严格绘于根结点的左边；将所有右子树都严格绘于根结点的右边。

然后假设现在有一个光源从该二叉树的顶部投射下来，那么所有结点在地平线上一定会有相应的投影，从左至右顺序读出投影结点的数据即为该二叉树的中序遍历序列。

如图11.10所示。

图示的中序遍历序列： D J G B H E A F I C
2.先序遍历的填空法
如果给定一棵二叉树的图形形态，可在图形基础上，采用填空法迅速写出该二叉树的先序遍历序列。

具体做法是：我们知道，对于每个结点都由三个要素组成，即根结点，左子树、右子树；又已知先序遍历顺序是先访问根结点、然后访问左子树、访问右子树。

那么，我们按层分别展开，逐层填空即可得到该二叉树的先序遍历序列。

图11.10 中序遍历投影法示意图
如图11.10 中的二叉树采用填空法的步骤如下：
(1)根结点左子树右子树
A( )( )
(2)A （根结点（左子树）（右子树））（根结点（左子树）（右子树））
A B C
(3)A(B(根结点（左）（右）)(根结点（左）（右）))（C(……)(……)）
A B D 无 G E H 无 C F 无
(4)A B D G J E H C F I 此即为该二叉树的先序遍历序列。

注：后序遍历的序列亦可以此方法类推，请读者自己尝试。

3.利用遍历序列构造二叉树
如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可以用这两个遍历序列构造一棵唯一的二叉树形态。

我们知道任意一棵二叉树的先序遍历序列和中序遍历序列是唯一的，那么首先从给定的先序遍历序列入手，该先序序列的第一个元素一定是该二叉树的根；再分析这个根结点在中序遍历序列中的位置，中序遍历序列中根结点的左边即为左子树的全部元素，而根结点的右边即为右子树的全部元素；然后据此再将先序遍历序列除根结点以外的其余部分分为左、右子树两部分，并在这两部分中分别找出左、右子树的根结点。

依此类推，即可得到完整的二叉树。

例11.1 已知一棵二叉树的先序遍历和中序遍历序列分别为：
先序： A B C I D E F H G
中序： C I B E D A H F G
请构造这棵二叉树。

按前述分析，这棵二叉树的构造过程如图11.11所示
图11.11 二叉树的构造过程
树、森林与二叉树的转换(flash演示)
如前所述，树（或森林）的存储结构及其操作算法的实现，由于其“度”的不确定性而导致其存储结构不是较为复杂就是浪费空间，因而，定义在其存储结构上的算法也相应地较难兼顾全面。

如果我们设定一定的规则，用二叉树来表示树和森林的话，就可以方便地解决树、森林的存储结构及其相关算法问题。

1.树、森林转换为二叉树
我们知道，一棵树中每个结点的孩子是无序的，而二叉树中各结点的孩子必须有左右之分。

在此，为避免概念混淆，首先约定树中每个结点的孩子按从左至右的顺序升序编号，即将树中同一层上的兄弟分出大小。

那么将一棵树转换成二叉树的方法是：
（1）在树中同层兄弟间加一连线；
（2）对树中每个结点仅保留其与长兄（左边第一个孩子）的连线，擦去其与其它孩子的连线；
（3）以树（或子树）的根作为轴心，将所有的水平连线顺时针旋转45度，即可得到与该树完全等价的一棵二叉树。

图11.12 树转换为二叉树的过程示意图
可以证明，转换得到的二叉树形态是唯一的。

转换过程如图11.12所示。

森林转换为二叉树的过程与树的转换过程基本相似，区别如下：
（1）将森林中每棵树的根结点间加一连线；
（2）转换后的二叉树不唯一，二叉树的形态取决于森林中树的初始摆放位置；
（3）树转换成二叉树后根结点没有右子树，而森林转换成二叉树后根结点有右子树。

2.将二叉树还原为树或森林
由上述转换过程可知：将二叉树还原为树或森林是上述过程的逆过程。

只是在转换时应注意树和森林转换为二叉树后的形态上的重要区别在于根结点是否具有右子树。

还原的具体步骤如下：
（1）若某结点是其双亲结点的左孩子，则将该结点的右孩子、右孙子、右重孙子……都与该结点的双亲用连线连起来；
（2）删去所有右孩子、右孙子……与其现在双亲结点的连线；
（3）将所有结点以其现在新的连接线所连接的结点为轴心，逆时针旋转45度。

这样即可得到还原后的树或森林。

如图11.13所示
图11.13 二叉树还原为树的过程示意图。