Question

森林转化为二叉树的方法

Answer 1

森林转化为二叉树的方法如下：

1、先把每棵树转换为二叉树；

2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

将一棵树转换为二叉树的方法是：

1、树中所有相邻兄弟之间加一条连线。

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

3、以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。

由于树中每个结点可能有多棵树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。

 

把每个结点的还结点排列起来，看成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表（叶子的孩子链表位空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。

 

森林转化为二叉树其目的是为了便于计算，树的孩子兄弟链表表示法和二叉树链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题