如何理解Java中的树(java,web开发)

1 树的定义

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

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

树的血缘关系

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

树的家族等级

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

2 树的存储结构

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

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

双亲表示法

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

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

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

孩子表示法

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

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

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

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

孩子兄弟表示法

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

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

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

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

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

3 树的遍历

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

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

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

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

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

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

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

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

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

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

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

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

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

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