树

前面讲到的顺序表、栈和队列都是一对一的线性结构，这节讲一对多的线性结构——树。「一对多」就是指一个元素只能有一个前驱，但可以有多个后继。

一、基本概念

树（tree）是n（n>=0）个结点的有穷集。n=0时称为空树。在任意一个非空树中：（1）每个元素称为结点（node）；（2）仅有一个特定的结点被称为根结点或树根（root）。（3）当n>1时，其余结点可分为m（m≥0）个互不相交的集合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作根的子树（subtree）。

注意：

n>0时，根节点是唯一的。

m>0时，子树的个数没有限制，但它们一定是互不相交的。

结点拥有的子树数被称为结点的度（Degree）。度为0的结点称为叶节点（Leaf）或终端结点，度不为0的结点称为分支结点。除根结点外，分支结点也被称为内部结点。结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲或父结点。同一个双亲的孩子之间互称为兄弟。树的度是树中各个结点度的最大值。

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。如果将树中结点的各个子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。森林是m（m>=0）棵互不相交的树的集合。

树的定义：

二、树的存储结构

由于树中每个结点的孩子可以有多个，所以简单的顺序存储结构无法满足树的实现要求。下面介绍三种常用的表示树的方法：双亲表示法、孩子表示法和孩子兄弟表示法。

1、双亲表示法

由于树中每个结点都仅有一个双亲结点（根节点没有），我们可以使用指向双亲结点的指针来表示树中结点的关系。这种表示法有点类似于前面介绍的静态链表的表示方法。具体做法是以一组连续空间存储树的结点，同时在每个结点中，设一个「游标」指向其双亲结点在数组中的位置。由于根结点没有双亲结点，我们约定根节点的parent域值为-1。树的双亲表示法如下所示：

双亲表示法

这样的存储结构，我们可以根据结点的parent域在O(1)的时间找到其双亲结点，但是只能通过遍历整棵树才能找到它的孩子结点。一种解决办法是在结点结构中增加其孩子结点的域，但若结点的孩子结点很多，结点结构将会变的很复杂。

2、孩子表示法

由于树中每个结点可能有多个孩子，可以考虑用多重链表，即每个结点有多个指针域，每个指针指向一个孩子结点，我们把这种方法叫多重链表表示法。它有两种设计方案：

方案一：指针域的个数等于树的度。

对于上一节中的树，树的度为3，其实现为：

方案一

显然，当树中各结点的度相差很大时，这种方法对空间有很大的浪费。

方案二，每个结点指针域的个数等于该结点的度，取一个位置来存储结点指针的个数。

对于上一节中的树，这种方法的实现为：

方案二

这种方法克服了浪费空间的缺点，但由于各结点结构不同，在运算上会带来时间上的损耗。

为了减少空指针的浪费，同时又使结点相同。我们可以将顺序存储结构和链式存储结构相结合。具体做法是：把每个结点的孩子结点以单链表的形式链接起来，若是叶子结点则此单链表为空。然后将所有链表存放进一个一维数组中。这种表示方法被称为孩子表示法。其结构为：

孩子表示法

这种结构对于查找某个结点的孩子结点比较容易，但若想要查找它的双亲或兄弟，则需要遍历整棵树，比较麻烦。可以将双亲表示法和孩子表示法相结合，这种方法被称为双亲孩子表示法。其结构如下：

双亲孩子表示法

其代码和孩子表示法的基本相同，只需在Node结点中增加parent域即可。

3、孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在则是唯一的，它的右兄弟如果存在也是唯一的。因此，我们可以使用两个分别指向该结点的第一个孩子和右兄弟的指针来表示一颗树。

其结构如下：

孩子兄弟表示法

这个方法，可以方便的查找到某个结点的孩子，只需先通过firstChild找到它的第一个孩子，然后通过rightSib找到它的第二个孩子，接着一直下去，直到找到想要的孩子。若要查找某个结点的双亲和左兄弟，使用这个方法则比较麻烦。

这个方法最大的好处是将一颗复杂的树变成了一颗二叉树。这样就可以使用二叉树的一些特性和算法了。