导读
在实际应用(如文件目录树)中,我们遇到的除了树形结构之外,还会遇到森林。直接对森林的操作会更加困难,因此通常会将森林转换为二叉树进行结点的操作。这样,我们通过树与二叉树的转换,森林与二叉树的转换,最后就能实现树与森林的转换。
森林转换为二叉树
森林是由若干棵树组成的,如果给这些树添加一个根结点,就变为一棵树。因此完全可以理解为,森林中的每一个棵树都是兄弟,所以可以按照兄弟的处理办法来操作森林。步骤如下:
* 步骤1 将森林中的每棵树变为二叉树;
* 步骤2 因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。
如下图所示:
二叉树转换为森林
判断二叉树转换为树还是森林,标准很简单,那就是看这颗二叉树的根结点有没有右孩子,有就是森林,没有就是树。那么如果转换为森林,步骤如下:
* 步骤1 从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除……,直到所有这些根节点与右孩子的连线都删除为止;
* 步骤2 将每棵分离后的二叉树转换为树。
如下图所示: