树、森林、二叉树之间的转换
树到二叉树的转换
基于树的孩子兄弟表示法，可以将一棵树转化为二叉树的形式。具体转化方式为：在所有兄弟结点之间加一条线；对于每个结点，除了保留其与长子的连线，去掉该节点与其他孩子的连线。
注意，这里沿用了孩子兄弟表示法的存储形式，即对于一个节点，其孩子节点在左侧指针，兄弟结点在右侧指针。即使这棵树本身就是二叉树，其也可以经过转化变成我们需要的二叉树。
森林到二叉树的转换
- 将森林中的每一棵树都转化为二叉树。
- 接着将每个二叉树的根节点视为兄弟节点，继续用孩子兄弟表示法连在一起，即从第一棵树开始不断向右拓展。
二叉树到树、森林的转换
- 如果一个二叉树的根节点有右孩子，则说明这个二叉树是由森林转换成的。要想将二叉树转换回去，需要先断开所有根节点与根节点右孩子之间的线，形成多个二叉树，每个二叉树可转化为一棵树。
- 对于一棵树对应的二叉树来说，其每个节点，左侧节点是下一层，右侧节点是同一层。因此对于每个节点，可以将其所有的右侧节点与其双亲节点连接，同时断开其与右侧节点的连线。去掉所有双亲到右孩子的连线。
- 任何一棵与树对应的二叉树，其右子树必为空。
树或森林与二叉树之间有一个自然的一一对应的关系。任何一个森林或树可以唯一地对应到一棵二叉树；任何一棵二叉树可以唯一地对应到一个森林或一棵树。
链接到
- 上一个知识点：6.8 线索二叉树
- 下一个知识点：6.10 树和森林的遍历