1. 树、森林的转换
(1) 利用孩子兄弟表示法，所有的树都可以用二叉树表示。
(2) 森林由多棵树组成，所有树转化二叉树之后，将他们的根节点作为兄弟结点，再用孩子兄弟表示法，结合成一个二叉树。
2. 树和二叉树的转换
(1) 在兄弟结点之间加一连线
(2) 每一结点只保留与第一个结点的连线，其他的抹掉
(3) 以树根为轴心，顺时针旋转45°
关于第三步：其实就是把形成的新树按照二叉树的样子进行摆设（除了看起来顺眼一点，毫无意义）见下图
Paste_Image.png
此处提到的，树转换而成的二叉树其右子树一定为空，道理很简单，右孩子是结点的兄弟结点，而树的根节点是不可能存在兄弟结点的。
3. 树和森林的遍历
(1) 树的遍历：先根遍历，后根遍历。访问根结点的先后
(2) 森林遍历：先序遍历（从第一棵树开始，挨着先序遍历），中序遍历（从第一棵树开始，挨着后序遍历）。
4. 遍历的等价关系
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
森林的先序遍历就是把所有树先根遍历一遍
森林的中序遍历就是把所有树后根遍历一遍，所以转变成二叉树的遍历方法一样。
网友评论