树转换为二叉树

（1）加线。在所有兄弟结点之间加一条连线。

（2）去线。树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结点之间的连线。

（3）层次调整。以树的根节点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。（注意第一个孩子是结点的左孩子，兄弟转换过来的孩子是结点的右孩子）

森林转换为二叉树

（1）把每棵树转换为二叉树。

（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。

二叉树转换为树

是树转换为二叉树的逆过程。

（1）加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

（2）去线。删除原二叉树中所有结点与其右孩子结点的连线。

（3）层次调整。

二叉树转换为森林

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

（1）从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。

（2）将每棵分离后的二叉树转换为树。

课后习题

【2014年真题】将森林 F 转换为对应的二叉树 T，F 中叶结点的个数等于（）
A．T 中叶结点的个数         B．T 中度为 1 的结点个数 
C．T 中左孩子指针为空的结点个数     D．T 中右孩子指针为空的结点个数

参考答案：C
答案解析：将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林 某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F 中叶结点的个数就等于 T 中左孩子指针为空的结点个数，选 C。 
此题还可以通过一些特例来排除 A、B、D 选项。 

【2011年真题】已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（）
A．115
B．116
C．1895
D．1896 

解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二 
叉树中仅有前115个叶结点有右孩子。

【2009年真题】将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u和 v 可能具有的关系是（）。 
Ⅰ．父子关系 Ⅱ．兄弟关系 
Ⅲ．u 的父结点与 v 的父结点是兄弟关系 
A． 只有Ⅱ B．Ⅰ和Ⅱ C．Ⅰ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ

参考答案：B
答案解析：考查森林和二叉树的转换。 
森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。 
情形Ⅰ：若结点 v 是结点 u 的第二个孩子结点，在转换时，结点 v 就变成结点 u 第一个孩子的右孩子，符合要求。 
情形Ⅱ：结点 u 和 v 是兄弟结点的关系，但二者之中还有一个兄弟结点 k，则转换后，结点 v 就变为结点 k 的右孩子，而结点 k 则是结点 u 的右孩子，符合要求。 
情形Ⅲ：结点 v 的父结点要么是原先的父结点或兄弟结点。若结点 u 的父结点与 v 的父结点是兄弟关系，则转换之后，不可能出现结点 u 是结点 v 的父结点的父结点。