树转换为二叉树

森林转换为二叉树

树的遍历

树的遍历有两种方式：先序遍历和后序遍历。

先序遍历是先访问根结点，再依次访问根结点的每棵子树，访问子树时仍然遵循先根再子树的规则。

后序遍历是先依次访问根结点的每棵子树，再访问根结点，访问子树时仍然遵循先子树再根的规则。

以下图为例：

先序遍历：

• 1)访问根结点A。
• 2)访问A的第一棵子树，访问子树时先访问根结点B.
• 3)访问B的第一个孩子E.
• 4) 访问B的第二个孩子 F.
• 5)访问A的第二棵子树，访间子树时先访问根结点C。
• 6)访问C的第一个孩子 G.
• 7)访间A的第三棵子树，访间子树时先访问根结点D.
• 8)访问D的第一个孩子H。
• 9)访问D的第二个孩子I。
• 10)访问D的第三个孩子J。

先序遍历的结果为ABEFCGDHIJ。

后序遍历：

• 1)访问根结点A的第一棵子树，访问子树时先访问根B的第一个孩子E.
• 2)访问B的第二个孩子F.
• 3)访问B.
• 4)访问A的第二棵子树，访问子树时先访问根C的第一个孩子G.
• 5)访问C.
• 6)访问A的第三棵子树，访问子树时先访问根D的第一个孩子H。
• 7)访问D的第二个孩子I。
• 8)访问D的第三个孩子J。
• 9)访问D。
• 10)最后访问根结点A.

后序遍历的结果为EFBGCHIJDA。

树与二叉树遍历的关系：

树转换为二叉树后，树的先序遍历对应二叉树的先序遍历，树的后序遍历对应二叉树的中序遍历(注意不是后序遍历)。所以，可以将树转换为二叉树后，借助遍历二叉树的方法来遍历树。假如一棵树已经转化为二叉树来存储，要得到其先序遍历序列，只需先序遍历这棵二又树:要得到其后序遍历序列只需中序遍历这棵二叉树。

图解如下：

森林的遍历

森林的遍历方式有两种:先序遍历和后序遍历。

先序遍历的过程:先访间森林中第一棵树的根结点， 然后先序遍历第棵树中根结点的子树， 最后先序遍历森林中除了第一棵树以外的其他树。

后序遍历的过程:后序遍历第一棵树中根结点的子树， 然后访问第一棵树的根结点， 最后后序遍历森林中除去第一棵树以后的森林。

森林转换为二叉树中，森林的先序遍历对应二叉树的先序遍历，森林的后序遍历对应二叉树的中序遍历。

图解如下：