阅读:0       作者:严长生

森林转化为二叉树(详解版)

前面介绍了普通转化为二叉树孩子兄弟表示法,本节来学习如何将森林转化为一整棵二叉树。

森林,指的是由 n(n>=2)棵互不相交的树组成的集合,如 1 所示。

森林示意图
图 1 森林示意图

在某些实际场景中,为了便于操作具有森林结构的数据,往往需要将森林转化为一整棵二叉树。

我们知道,任意一棵普通树都可以转化为二叉树,而森林是由多棵普通树构成的,因此自然也可以转化为二叉树,其转化方法是:
  1. 首先将森林中所有的普通树各自转化为二叉树;
  2. 将森林中第一棵树的树根作为整个森林的树根,其他树的根节点看作是第一棵树根节点的兄弟节点,采用孩子兄弟表示法将所有树进行连接;

例如,将图 2a) 中的森林转化为二叉树,则以上两个转化过程分别对应图 2 中的 b) 和 c) :

森林转化为二叉树的过程示意图
图 2 森林转化为二叉树的过程示意图

如图 2 所示,先将森林包含的所有普通树各自转化为二叉树,然后将其他树的根节点看作为第一棵二叉树的兄弟节点,采用孩子兄弟表示法进行连接。

森林转化为二叉树,更多的是为了对森林中的节点做遍历操作。前面讲过,遍历二叉树有 4 种方法,分别是层次遍历、先序遍历、中序遍历和后序遍历。转化前的森林与转化后的二叉树相比,其层次遍历和后序遍历的访问节点顺序不同,而前序遍历和中序遍历访问节点的顺序是相同的。

以图 1 中的森林为例,其转化后的二叉树为图 2c),两者比较,其先序遍历访问节点的顺序都是 A B C D E F G H I J;同样,中序遍历访问节点的顺序也相同,都是 B C D A F E H J I G。而后序遍历和层次遍历访问节点的顺序是不同的。

提示,由二叉树转化为森林的过程也就是森林转化二叉树的逆过程,也就是图 2 中由 c) 到 b) 再到 a) 的过程。