说起树，想必大多数人第一反应都是二叉树以及二叉树的各种亲戚，包括红黑树、平衡二叉树等。但是其实除了二叉树外，普通的树结构在数据结构中也占据着非常重要的一部分。

不仅如此，所谓百川成海，白木成林。既然有了树结构，自然而然也会有相应的森林结构。因此，本文就将从普通的树结构出发，探讨并介绍一下树和森林的那些事。

 1   树的定义

树实际上就是由许多个节点组成的集合，只不过每个节点的的组成是根据树状结构进行划分。一颗普通的树结构可以通过以下图来定义。

还是再来罗嗦一遍，树的结构就像是一颗倒挂的树，结点的组成是以层级往下。一棵树由若干子树构成，而子树又有更小的子树构成。

树的血缘关系

对于树中的某个结点，最多只和上一层的结点有直接的关系，而与其下一层的多个结点有直接关系。其上一层的结点称为双亲结点，下一层的结点称为孩子结点。所有位于树的最底部，没有孩子结点的结点被称之为叶子节点。具有相同双亲的结点互为兄弟节点。

树的家族等级

树是一个大家族，等级十分森严。树中某个结点的子树个数称为该结点的度。所以叶子结点也就是度为0的结点。而度不为0的结点被称之为内部结点。每一个结点都具有自己的层次，该层次由高往低递增，根结点为第一层，根的孩子结点为第二层，依次类推。一棵树最大的层数称之为树的高度（或深度）。

 2   树的存储结构

由于普通的树结构并不像二叉树那么规则，可能是多叉树的组合，因此很难用常规的线性结构来存储。因此树结构的存储需要将树家族中的关系剥离出来进行存储，保存了每个结点之间的关系，整个树结构也就能依次进行恢复。

这就好比家族中的族谱一样，记录的是我们和双亲以及兄弟姐妹的关系。对于树而言，则根据存储关系的不同，可分为双亲表示、孩子表示以及孩子兄弟表示三种存储方法。

双亲表示法

树的双亲表示，显然就是通过记录每个结点的双亲结点来存储整颗树的层次关系。这里常用的一种存储结构就是数组。在连续的地址中存储树的结点，同时将之与其双亲结点在数组中的序号进行对应，这样一来就能够保存所有结点的双亲信息。

双亲表示法直接存储的是结点的双亲位置（对应于数组的下标），因此在求某个结点的双亲结点以及祖先结点时非常方便。但是却无法直接获得该结点的孩子结点的位置。

若需要查找指定结点的孩子以及后代结点，需要遍历整个数组并进行多次判断才行。

孩子表示法

树的双亲表示法的缺点显而易见，所以最直接的解决办法就是干脆存孩子结点算了。还别说，孩子表示法就是这样一种表示方法。但是相较于双亲结点的存储，存储孩子结点有一个需要考虑的问题，就是某个结点的双亲结点最多只有一个，但是其孩子结点可能有多个。如果每个孩子结点都存储在数组里，这样的方式不是一个明智的选择，并且也没有必要。

所以在使用孩子表示法来存储树的结构时，常使用数组+链表的结构。这种结构是不是很常见，跟解决哈希冲突的链地址法有异曲同工之意。在这样的链式结构中，用指针指示出结点的每个孩子，每个孩子的位置通过链表依次相连，这样就十分方便与查找每个结点的子孙。

只不过问题依旧，若要找出寻找某个结点的双亲则同样需要遍历所有链表。不过，既然双亲表示和孩子表示都有了，简单粗暴的合并一下不就可以相互补充，共同进退吗。

所谓的双亲孩子表示法，直接将双亲表示和孩子表示组合起来即可。这样即可满足双亲的查找，也可以满足孩子的查找。

孩子兄弟表示法

本来有了双亲孩子表示法就已经足够用来存储树中的数据信息了，为什么还要来一个孩子兄弟法呢？其实不然，孩子兄弟表示法反而是一种很有意思且很有价值的表示方式。

在孩子兄弟表示法中，我们约定只存储每个结点的第一个孩子结点和下一个兄弟结点。不仅如此，结点的存储是通过链表进行的。话说不太清，还是直接看图吧。

看起来似乎有些诡异的形状，每个结点都作为链表的一个节点，通过两个指针分别指向第一个孩子结点和下一个兄弟结点。为了防止大家看不懂，我举个例子。拿结点B来说，它的第一个孩子结点是E，而它的下一个兄弟是与它处于同一层级的C。因此结点B的两个指针分别指向了E和C。

孩子兄弟表示法这样看起来似乎很鸡肋，但是假如我们调整一下右边这个图，就能看出其中的蹊跷了。

看出来了吗，孩子兄弟表示法实际上就是将一颗普通的树转换成了二叉树的形式。所以说二叉树为什么这么重要，因为万变不离其中呀。看到这，其实也透露出树和二叉树之间的转换关系，许多二叉树上的性质和操作也可以借此运用在普通的树结构中。

 3   树的遍历

学过二叉树的同学想必应该对前序遍历、中序遍历、后序遍历、中序遍历烂熟于心了吧，无论是迭代还是非迭代的写法，都是基础得不能再基础的东西了。而对于普通的树而言，由于每个结点子树的个数并不一定，因此不好规定前、中、后序的顺序。

所以一般而言对于树的遍历方式有两种，根据根结点被遍历的先后可分为先根遍历和后根遍历。

树的先根遍历是先访问树的根节点，然后依次遍历根结点的各个子树。如此递推。当将一颗普通树转换为对应的二叉树时（孩子兄弟表示法），其实就相当于是前序遍历。

树的后根遍历就不用多说了吧，跟先根遍历相反，先访问根结点的各颗子树，再访问树根结点。而树的后根遍历就相当于转换后二叉树的中序遍历。不信的话你试试。

 4   树、森林和二叉树的相互转换

写到这，突然发现好像忘记介绍森林是什么东西了。其实森林的概念很简单，就是很多颗树。对，就是这样。

树、森林和二叉树本质上都是类似的结构，因此相互之间可以进行转换。任意一个森林或者一棵树都可以对应表示为一颗二叉树，而任何一颗二叉树也能够对应到一个森林或一棵树上。

树转换为二叉树，我们在前面已经介绍过，就是通过树的孩子兄弟表示法。通过孩子兄弟法进行表示时，每一个树都可以用一颗唯一的二叉树来表示。但是转换过来的二叉树却有一个非常显著的特点。仔细观察。

很显然，这不是一颗平衡的二叉树。并且，根节点是没有右子树的，我敢肯定的说。这是因为根节点是没有兄弟结点的，它只有孩子结点，所以在转换为二叉树之后，一定是没有右子树的。

不过这样的缺陷可以在森林中进行弥补。由于森林中有很多棵树，因此可以将其它树作为右子树。具体的实现步骤，先将森林中的每一棵树转换为二叉树，再将第一颗树的根结点作为转换后的二叉树的根。第一棵树的左子树作为转换后二叉树根结点的左子树，第二棵树作为转换后二叉树的右子树。第三颗树作为转换后二叉树根结点的右子树的右子树。以此类推。

咱们来举个例子。这里有一个由三颗树构成的森林。

将上面三棵树分辨转换二叉树是以下形式。

然后将绿色二叉树作为蓝色二叉树根节点的右子树，将黄色二叉树作为绿色二叉树根节点的右子树，就可以得到森林转换为二叉树的结果。

根据以上的规则，同样可以将一颗二叉树转换为树和森林。

 5   总结

在数据结构中，估计树和森林不算很热门的结构，甚至许多工作过很多年的老码农都不曾用过。写这篇文章的时候，我也在想树和森林到底在实际中有什么用，似乎最重要的部分就是将一颗普通的树转换成二叉树来处理。但是我想这就是它的价值所在吧。

许多真实场景中，可能数据之间的关系并不能直接通过二叉树来表示和存储，一开始可能都需要通过多叉树或者各种畸形的树结构来定义关系。这样的树肯定是不适用于快速的处理和访问的，因此往往需要将这些奇形怪状的树转换为规则的二叉树来进行进一步的处理。最终为了回归到具体的应用，也需要将二叉树重新分解为最初的树或者森林结构来获得应用意义。

总的来说，存在即是真理。不怕用不到，就怕想不到。

 - end -