2.7　树结构

前面介绍的几种数据结构都属于线性结构，但是有些问题无法抽象为线性数据结构，例如，一个国家的行政机构、一个家族的家谱等。这些问题有个共同点，即可以表示成一个层次关系。这种层次关系可以抽象为树结构，这就是本节所要讲解的主要数据结构。

2.7.1　什么是树结构

树（Tree）结构是一种描述非线性层次关系的数据结构，其中重要的是树的概念。树是n个数据结点的集合，在该集合中包含一个根结点，根结点之下分布着一些互不交叉的子集合，这些子集合是根结点的子树。树结构的基本特征如下：

・在一个树结构中，有且仅有一个结点没有直接前驱，这个结点就是树的根结点；

・除根结点外，其余每个结点有且仅有一个直接前驱；

・每个结点可以有任意多个直接后继。

典型的树结构，如图2-13所示，可以直观地看到其类似于现实中树的根系，越往下层根系分支越多。图中A便是树的根结点，根结点A有三个直接后继结点B、C和D，而结点C只有一个直接前驱结点A。

另外，一个树结构也可以是空，此时空树中没有数据结点，也就是一个空集合。如果树结构中仅包含一个结点，那么这也是一个树，树根便是该结点自身。

从树的定义可以看出，树具有层次结构的性质。而从数学的角度来看，树具有递归的特性。在树中的每个结点及其之后的所有结点构成一个子树，这个子树也包括根结点。

2.7.2　树的基本概念

对于读者来说，树是一种全新的数据结构，其中包含了许多新的概念。

・父结点和子结点：每个结点子树的根称为该结点的子结点，相应的，该结点称为其子结点的父结点。

・兄弟结点：具有同一父结点的结点称为兄弟结点。

・结点的度：一个结点所包含子树的数量。

・树的度：是指该树所有结点中最大的度。

・叶结点：树中度为零的结点称为叶结点或终端结点。

・分支结点：树中度不为零的结点称为分支结点或非终端结点。

・结点的层数：结点的层数从树根开始计算，根结点为第1层、依次向下为第2、3、……、n层（树是一种层次结构，每个结点都处在一定的层次上）。

・树的深度：树中结点的最大层数称为树的深度。

・有序树：若树中各结点的子树（兄弟结点）是按一定次序从左向右排列的，称为有序树。

・无序树：若树中各结点的子树（兄弟结点）未按一定次序排列，称为无序树。

・森林（forest）：n（n>0）棵互不相交的树的集合。

下面从一个例子来分析上述树结构的基本概念。图2-14所示为一个基本的树结构。其中，结点A为根结点。结点A有3个子树，因此，结点A的度为3。同理，结点E有两个子树，结点E的度为2。所有结点中，结点A的度为3最大，因此整个树的度为3。结点E是结点K和结点L的父结点，结点K和结点L是结点E的子结点，结点K和结点L为兄弟结点。

在这个树结构中，结点G、结点H、结点K、结点J、结点N、结点O、结点P和结点Q都是叶结点。其余的都是分支结点，整个树的深度为4。除去根结点A，留下的子树就构成了一个森林。

由于树结构不是一种线性结构，很难用数学式子来表示，这就需要采用全新的方式来表示树。一般来说，常采用层次括号法。层次括号法的基本规则如下：

・根结点放入一对圆括号中；

・根结点的子树由左至右的顺序放入括号中；

・对子树做上述相同的处理。

这样，同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。按照这种方法，图2-13所示的树结构可以表示成如下形式：

（A（B（E）），（C（F（J）），（G（K，L））），（D（H），（I（M，N））））

2.7.3　二叉树

在树结构中，二叉树是最简单的一种形式。在研究树结构时，二叉树是树结构内容中的重点。二叉树的描述相对简单，处理也相对简单，而且更为重要的是任意的树都可以转换成对应的二叉树。因此，二叉树是所有树结构的基础。

1.什么是二叉树

二叉树是树结构的一种特殊形式，它是n个结点的集合，每个结点最多只能有两个子结点。二叉树的子树仍然是二叉树。二叉树的一个结点上对应的两个子树分别称为左子树和右子树。由于子树有左右之分，因此二叉树是有序树。

从上述定义可以看出，在普遍的树结构中，结点的最大度数没有限制，而二叉树结点的最大度数为2。另外，树结构中没有左子树和右子树的区分，而二叉树中则有此区别。

一个二叉树结构也可以是空，此时空二叉树中没有数据结点，是一个空集合。如果二叉树结构中仅包含一个结点，那么这也是一个二叉树，树根便是该结点自身。

另外，依照子树的位置的个数，二叉树还有如下几种形式，如图2-15所示。

其中，对于图（a），只有一个子结点且位于左子树位置，右子树位置为空；对于图（b），只有一个子结点且位于右子树位置，左子树位置为空；对于图（c），具有完整的两个子结点，即左子树和右子树都存在。

对于一般的二叉树，在树结构中可能包含上述各种形式。按照上述二叉树的这几种形式，为了研究的方便，二叉树还可以进一步细分为两种特殊的类型，满二叉树和完全二叉树。

满二叉树即在二叉树中除最下一层的叶结点外，每层的结点都有两个子结点。典型的满二叉树，如图2-16所示。

完全二叉树即在二叉树中除二叉树最后一层外，其他各层的结点数都达到最大个数，且最后一层叶结点按照从左向右的顺序连续存在，只缺最后一层右侧若干结点。典型的完全二叉树，如图2-17所示。

从上述满二叉树和完全二叉树的定义可以看出，满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树，因为其没有达到完全满分支的结构。

2.完全二叉树的性质

二叉树中树结构研究的重点是完全二叉树。对于完全二叉树，若树中包含n个结点，假设这些结点按照顺序方式存储。那么，对于任意一个结点m来说，具有如下性质：

・如果m！=1，则结点m的父结点的编号为m/2；

・如果2*m≤n，则结点m的左子树根结点的编号为2*m；若2*m>n，则无左子树，也没有右子树；

・如果2*m+1≤n，则结点m的右子树根结点编号为2*m+1；若2*m+1>n，则无右子树。

另外，对于该完全二叉树来说，其深度为[log2n]+1。

这些基本性质展示了完全二叉树结构的特点，在完全二叉树的存储方式及运算处理上都有重要意义。

按照数据的存储方式，树结构可以分为顺序存储结构和链式存储结构两种。接下来分析这两种存储方式的实现。

3.二叉树的顺序存储

顺序存储方式是最基本的数据存储方式。与线性表类似，树结构的顺序存储一般采用一维结构数组来表示。这里的关键是定义合适的次序来存放树中各个层次的数据。

先来分析完全二叉树的顺序存储，如图2-18所示，左侧是一个典型的完全二叉树，每个结点的数据为字符类型。如果采用顺序存储方式，可以将其按层来存储，即先存储根结点，然后从左至右依次存储下一层结点的数据……，直到所有的结点数据完全存储。图2-18右侧所示为这种存储的形式。

上述完全二叉树顺序存储结构的数据定义，可以采用如下形式：

static final int MAXLen=100；　　//最大结点数

char[] SeqBinTree=new char[MAXLen]；　　//定义保存二叉树数组

其中，元素类型是每个结点的数据类型，这里是简单的字符型。对于复杂的数据，读者也可以采用自定义的对象，这样保存完全二叉树的数据成为对象数组。

可以根据前面介绍的完全二叉树的性质来推算各个结点之间的位置关系。例如：

・对于结点D，其位于数组的第4个位置，则其父结点的编号为4/2=2，即结点B。

・结点D左子结点的编号为2*4=8，即结点H。

・结点D右子结点的编号为2*4+1=9，即结点I。

非完全二叉树的存储要稍复杂些。为了仍然可以使用上述简单有效的完全二叉树的性质，将一个非完全二叉树填充为一个完全二叉树，如图2-19所示。图2-19（a）为一个非完全二叉树，将缺少的部分填上一个空的数据结点来构成图2-19（b）的完全二叉树。

这样，再按照完全二叉树的顺序存储方式来存储，如图2-20所示。下面便可以按照前述的规则来推算结点之间的关系了。

但是，这种方式有很大的缺点，即浪费存储空间，这是因为其中填充了大量的无用数据。因此，顺序存储方式一般只适用于完全二叉树的情况。对于其他的情况，一般采用链式存储方式。

4.二叉树的链式存储

与线性结构的链式存储类似，二叉树的链式存储结构包含结点元素及分别指向左子树和右子树的引用。典型的二叉树的链式存储结构，如图2-21所示。

二叉树的链式存储结构定义代码示例如下：

有时候，为了后续计算的方便，也可以保存一个该结点的父结点的引用。此时二叉树的链式存储结构包含了结点元素、指向父结点的引用及分别指向左子树和右子树的引用。这种带父结点的二叉树链式存储结构，如图2-22所示。

带父结点的二叉树链式存储结构定义代码示例如下：

接下来将分析如何在Java语言中建立二叉树结构，并完成二叉树结构的基本运算。

2.7.4　准备数据

学习了前面的理论知识后，下面就开始二叉树结构的程序设计。首先需要准备数据，即准备在二叉树结构操作中需要用到的变量及类等。示例代码如下：

在上述代码中，定义了二叉树结构的类CBTType。结点的具体数据保存在一个字符串data中，而引用left用来指向左子树结点，引用right用来指向右子树结点。

2.7.5　初始化二叉树

在使用顺序表之前，首先要初始化二叉树。在此，在程序中只需将一个结点设置为二叉树的根结点。代码示例如下：

在上述代码中，首先申请内存，然后由用户输入一个根结点数据，并将指向左子树和右子树的引用设置为空，即可完成二叉树的初始化工作。

2.7.6　添加结点

添加结点即在二叉树中添加结点数据。添加结点时除了要输入结点数据外，还需要指定其父结点，以及添加的结点是作为左子树还是作为右子树。添加结点的代码示例如下：

在上述代码中，输入参数treeNode为二叉树的根结点，参数传入根结点是为了方便在代码中进行查找。程序中首先申请内存，然后由用户输入二叉树结点数据，并设置左、右子树为空。接着指定其父结点，最后设置其作为左子树还是作为右子树。

2.7.7　查找结点

查找结点即在二叉树中的每一个结点中，逐个比较数据，当找到目标数据时将返回该数据所在结点的引用。查找结点的代码示例如下：

在上述代码中，输入参数treeNode为待查找的二叉树的根结点，输入参数data为待查找的结点数据。程序中首先判断根结点是否为空，然后分别向左、右子树递归查找。如果当前结点的数据与查找数据相等，则返回当前结点的引用。

2.7.8　获取左子树

获取左子树即返回当前结点的左子树结点的值。由于在二叉树结构中定义了相应的引用，因此，该操作比较简单。获取左子树的示例代码如下：

在上述代码中，输入参数treeNode为二叉树的一个结点。该程序将返回该结点的左子树的引用。

2.7.9　获取右子树

获取右子树即返回当前结点的右子树结点的值。由于在二叉树结构中定义了相应的引用，因此，该操作比较简单。获取右子树的示例代码如下：

在上述代码中，输入参数treeNode为二叉树的一个结点。该程序将返回该结点的右子树的引用。

2.7.10　判断空树

判断空树即判断一个二叉树结构是否为空。如果是空树，则表示该二叉树结构中没有数据。判断空树的代码示例如下：

在上述代码中，输入参数treeNode为待判断的二叉树的根结点。该函数检查二叉树是否为空，为空则返回1，否则返回0。

2.7.11　计算二叉树深度

计算二叉树深度即计算二叉树中结点的最大层数，这里往往需要采用递归算法来实现。计算二叉树深度的示例代码如下：

在上述代码中，输入参数treeNode为待计算的二叉树的根结点。程序中首先判断根结点是否为空，然后分别按照递归调用来计算左子树深度和右子树深度，从而完成整个二叉树深度的计算。

2.7.12　清空二叉树

清空二叉树即将二叉树变成一个空树，这里也需要使用递归算法来实现。清空二叉树的示例代码如下：

在上述代码中，输入参数treeNode为待清空的二叉树的根结点。程序中按照递归调用来清空左子树和右子树，并且使用赋值null操作来释放当前结点所占内存，从而完成清空操作。

2.7.13　显示结点数据

显示结点数据即显示当前结点的数据内容，此操作比较简单。显示结点数据的代码示例如下：

在上述代码中，输入参数p为待显示的结点。在程序中，直接使用printf方法输出该结点数据。

2.7.14　遍历二叉树

遍历二叉树即逐个查找二叉树中所有的结点，这是二叉树的基本操作，因为很多操作都需要首先遍历整个二叉树。由于二叉树结构的特殊性，往往可以采用多种方法进行遍历。

由于二叉树代表的是一种层次结构，因此，首先按层来遍历整个二叉树。对于二叉树的按层遍历，一般不能使用递归算法来编写代码，而是使用一个循环队列来进行处理。首先将第1层（根结点）进入队列，再将第1层根结点的左右子树（第2层）进入队列……，循环处理，可以逐层遍历。

上述按层遍历有点复杂，也可以使用递归来简化遍历算法。首先来分析一个二叉树中的基本结构，如图2-23所示。这里D表示根结点，L表示左子树，R表示右结点。一般可以采用如下几种方法来遍历整个二叉树：

・先序遍历：即先访问根结点，再按先序遍历左子树，最后按先序遍历右子树。先序遍历一般也称为先根次序遍历，简称为DLR遍历。

・中序遍历：即先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。中序遍历一般也称为中根次序遍历，简称为LDR遍历。

・后序遍历：即先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。后序遍历一般也称为后根次序遍历，简称为LRD遍历。

先序遍历、中序遍历和后序遍历的最大好处是可以方便地利用递归的思想来实现遍历算法。下面详细介绍这几种遍历算法的代码实现。

1.按层遍历算法

按层遍历算法是最直观的遍历算法。首先处理第1层即根结点，再处理第1层根结点的左右子树，即第2层……，循环处理，就可以逐层遍历。按层遍历算法的代码示例如下：

在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。程序在整个处理过程中，首先从根结点开始，将每层的结点逐步进入队列，这样就可得到按层遍历的效果。

2.先序遍历算法

先序遍历算法即先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。程序中可以按照递归的思路来遍历整个二叉树。先序遍历算法的示例代码如下：

在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。

3.中序遍历算法

中序遍历算法即先访问根结点，再按先序遍历左子树，最后按先序遍历右子树。程序中可以按照递归的思路来遍历整个二叉树。中序遍历算法的示例代码如下：

在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。

4.后序遍历算法

后序遍历算法即先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。程序中可以按照递归的思路来遍历整个二叉树。后序遍历算法的示例代码如下：

在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。

2.7.15　树结构操作实例

学习了前面的树结构的基本运算，便可以轻松地完成对树结构的各种操作。下面给出一个完整的例子，来演示树结构的创建、插入结点和遍历等操作。代码示例如下：

【程序2-5】

在上述代码中，主方法首先初始化二叉树，设置根元素。然后由用户来选择添加结点的操作。接着，分别可以选择先序遍历、中序遍历、后序遍历和按层遍历4种方式来遍历整个二叉树。最后，输出该二叉树的深度，并清空二叉树，结束整个操作过程。

在程序执行时，首先初始化输入根结点为A，然后选择菜单“1”分别添加结点B为结点A的左子树，添加结点C为结点A的右子树……，整个程序的执行过程，如图2-24所示。添加完所有的结点后，选择菜单“0”便可以退出结点的添加过程，进而执行后面的程序。

程序接下来便是执行不同的二叉树遍历操作。按照菜单的指示分别选择先序遍历、中序遍历、后序遍历和按层遍历4种方式。程序执行的结果，如图2-25所示。读者可以结合这4种遍历算法的方法和程序代码，来理解遍历的结果。最后，用户输入菜单“0”退出遍历过程。程序最后输出该二叉树的深度为3，并清空整个二叉树，从而完成整个操作过程。