本文将详细介绍树这种数据结构的基本概念，以及通用的树的Java实现方式，为后面各种树的深入学习打好基础。

树结构和线性结构的最大的不同是，树中的节点具有明显的层级关系，并且一个节点可以对应多个节点。

1 树的概述

1.1 定义

树结构和线性结构的最大的不同是，树中的节点具有明显的层级关系，并且一个节点可以对应多个节点。树的定义如下：

树（Tree）是n（n≥0）个节点的有限集。n=0时称为空树。在任意一棵非空树中：

有且仅有一个特定的称为根（Root）的节点r；

当n＞1时，其余节点可分为m（m＞0）个互不相交的不为空的有限集T1、T2、……、Tm，其中每一个集本身又是一棵树，并且称为根的子树（SubTree）。

从上面树的定义可以看出使用了递归的思想，也就是在树的定义之中还用到了树的概念，根的子树节点，同时作为子树的根节点。递归思想和栈数据结构有关，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

如上图，该树具有唯一根节点r，它的子树是以a、b、c为根节点的三棵树。而子树a下面还有一颗子树d。

从递归中我们发现，一棵树是N个节点和N−1条边的集合，其中的一个节点叫做根。存在N−1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲。

1.2 节点

在上图中，节点r是根。节点a有一个父亲并且儿子d、e。每一个节点可以有任意多个儿子，也可能是零个儿子。没有儿子的节点称为树叶（leaf）；上图中的树叶是e、f、g、h、i、j和k。

具有相同父亲的节点称为兄弟（sibling），比如a、b和c节点都是兄弟节点；用类似的方法可以定义祖父（grandfather）和孙子（grandchild)。

森林：两颗或两颗以上互不相交的树的集合。

1.3 深度和高度

节点的层次（Level）从根开始定义起，这里规定，根为第一层，根的孩子为第二层。若某节点在第i层，则其子树就在第i+1层。树中节点的最大层次称为树的深度（Depth)或高度，上图中，树的深度为4。

本文约定：从上往下数就是深度，从下往上数就是高度。另外由于不同的参考书对于根节点深度和高度的定义不一样，而节点的深度和高度会受到根节点的深度0还是1的影响，本文取根节点深度为1。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高度。

上图中，根节点r的深度为1，高度为4。子节点b的深度为2，高度为2。

1.4 节点的度

树的节点包含一个数据元素及若干指向其子树的分支。节点拥有的直接子节点数称为该节点的度（De-gree）。

度为0的节点称为叶节点（Leaf)或终端节点；度不为0的节点称为非终端节点或分支节点。

除根节点之外，分支节点也称为内部节点。树的度是树内各节点的度的最大值。上图中，因为这棵树节点的度的最大值是节点r和d的度，为3，所以树的度也为3。

1.5 有序性

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。

2 树的通用实现

树也可以采用顺序存储结构和链式存储结构实现。下面有三种通用的树实现的方法。后面介绍特殊的树时，比如二叉树、红黑树等它们还有自己的特殊实现方式。

2.1 父节点表示法

采用顺序存储结构来实现树，底层采用数组来存储节点。由于子节点具有唯一的父节点，因此，可以采用父节点表示法表示出一棵树的结构。

节点由数据域和父节点的索引位置组成，根节点的父节点索引为-1。

上图的树，使用最简单的父节点表示法可以表示为：

index（数组索引）data（数据域）parent（父节点索引）0r-11a02b03c04d15e16f27g38h39i410j411k4

树节点的设计可以是：

/***树节点的设计**@param<E>E类型*/privatestaticclassTreeNode<E>{//数据域Ee;//父节点的索引intparent;publicTreeNode(Ee,intparent){this.e=e;this.parent=parent;}}

这样的存储结构，我们可以根据结点的parent索引很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。但是如果要知道孩子节点是什么，那就需要遍历整个数组才行。

2.2 父子节点链表示法

为了能够直观的找到一个节点的孩子节点。在原节点中添加一个子节点链表，原节点保存子节点链表的头索引，同时节点保存着父节点的索引。这需要一种新的孩子节点。

index（数组索引）data（数据域）parent（父节点索引）child（子节点链表头索引）0r-1a->b->c->null1a0d->e->null2b0f->null3c0g->h->null4d1i->j->k5e1null6f2null7g3null8h3null9i4null10j4null11k4null

树节点和子节点的设计可以为：

/***树节点的设计**@param<E>E类型*/privatestaticclassTreeNode<E>{//数据域Ee;//父节点的索引intparent;//第一个子节点的引用TreeNodeChild<E>firstChild;publicTreeNode(Ee,intparent,TreeNodeChild<E>firstChild){this.e=e;this.parent=parent;this.firstChild=firstChild;}}/***子节点链表结构**@param<E>*/privatestaticclassTreeNodeChild<E>{//子节点的索引intindex;//下一个子节点的索引TreeNodeChild<E>next;publicTreeNodeChild(intindex,TreeNodeChild<E>next){this.index=index;this.next=next;}}

2.3 父子兄弟表示法

对于上面的父节点表示法和父子节点表示法，不能很方便的得知节点的兄弟节点。

实际上，我们观察树形结构后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个索引，分别指向该结点的第一个孩子和此结点的右兄弟。只需要两个引用就能很方便的表示出节点的唯一对应关系。

为了突破节点数量限制，我们可以使用链表。为了找到父节点，我们还可以添加父节点索引。

data（数据域）parent（父节点引用）child（第一个子节点引用）right（节点右兄弟引用）rnullanullardbbrfccrgnulldaieeanullnullfbnullnullgcnullhhcnullnullidnulljjdnullkkdnullnull

节点可以统一设计为如下，不需要额外的节点结构：

/***树节点的设计**@param<E>E类型*/privatestaticclassTreeNode<E>{//数据域Ee;//父节点的引用(可选)TreeNode<E>parent;//第一个子节点的引用TreeNode<E>firstChild;//右兄弟节点的引用TreeNode<E>rightBrother;}

使用示意图来直观的展示这种表示法的效果：

图中只标出了子节点和兄弟节点的引用链，红色为子节点引用，黑色为右兄弟节点的引用。我们看到，只需要这两个引用关系就能表示出一颗完整的树。并且需要查找某个节点的子节点或者父节点或者兄弟节点时，不需要完整遍历整颗树。

上面的表示方法，每个节点最多包括两个引用节点（不计算父节点引用），实际上这样的表示方法，把复杂的多子节点的树，表示成了一颗简单的二叉树：

这种表示法将是以后最常用的方法，二叉树将是我们在以后用到的最多的树种之一。

3 总结

本文作为树这种数据结构的入门文章，详细讲解了树以及各种专业术语的定义和解释，然后讲解了树的通用实现，讲了父节点表示法、父子节点链表示法、父子兄弟表示法。实际上后面的特性化的数据结构比如二叉树、AVL树、红黑树，均有自己的表示方法。但是上面这几种方法作为树的通用实现，还是可以了解一下的。

最后提到了二叉树，二叉树将是我们在以后用到的最多的树种之一，内容非常繁多，在此不做介绍，本文作为树的入门文章，在后续的文章中，将慢慢介绍二叉树等特性化的树。

相关文章：

《大话数据结构》

《算法图解》

《算法》

作者：刘Java