二叉树与森林之间的转换
二叉树与森林之间也可以相互转换,森林可以转换为二叉树,二叉树也可以还原为森林。本节就来学习它们之间如何转换。
1、森林转换为二叉树
森林是树的有限集合,如图1所示是拥有三棵树的森林。
图1 森林
一棵树可以转换为二叉树,由二叉树转换的森林也可以还原为二叉树,将森林转换为二叉树的步骤如下所示:
(1)将森林中的每棵树都转换为相应的二叉树,形成有若干二叉树的森林,如图2所示。
图2 树转换成了相应二叉树
(2)按森林中树的先后次序,依次将靠后的一棵二叉树作为当前二叉树根结点的右子树,这样整个森林就转化成了一棵二叉树。如图3所示。
图3 森林转换为的二叉树
图3就是一棵由拥有三棵树的森林转换成的二叉树,这棵树的根结点就是森林中第一棵树的根结点。
2、二叉树转换为森林
二叉树能否转换为森林,取决于树的根结点是否有右子树,如果根结点没有右子树,则这棵二叉树只能转换为一棵树;如果根结点有右子树,则二叉树可以转换为森林。二叉树转换为森林也分为两个步骤,如下所示:
(1)判断树的根节点是否有右子树,若右子树存在,则把根结点与右子树根结点的连线删除。查看分离后的二叉树,若其根节点的右孩子存在,则连线删除……如此重复往右找,直到所有根节点与右孩子的连线都删除为止。以3中的二叉树为例,从根结点开始,一直删除结点与其右孩子之间的连线,如图4所示。
图4 断开结点与右孩子之间的连线
(2)将每棵二叉树转换为树。
经过步骤(1),生成了图4中的三棵二叉树。将这三棵二叉树转换为相应的树,这样就形成了拥有三棵树的森林。
二叉树与树、森林之间转换的思路比较简单,理解起来也很容易,稍作练习便能掌握。