@[toc]

本篇文章将讲解树和二叉树，因为树和二叉树涉及的内容较多，我将这些内容分为几篇文章来讲解。

树的定义

先看看树的官方定义：

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。

官方的解释总是让人难以理解，我们通过画图来理解一下：

对于树，我们需要注意几点：

• 当只有一个结点时，它也是一棵树

• 当结点大于一个时，树的根结点是唯一的，也就是说一棵树只能有一个根结点

• 同一层的结点互不相交，比如上面这棵树，结点B和结点C肯定不能相连，同样地，结点D、E、F之间也不能相互关联
• 每一个非根结点有且仅有一个父节点，比如结点D的父结点时结点B，它就不能去和结点C相连，否则它就有了两个父结点

结点的定义

再来看看对于树中结点的定义。

树的结点包含一个数据元素和若干指向子结点的分支，其中结点拥有的分支数称为结点的度，度为0的结点称为叶子结点或终端结点；度不为0的结点称为非终端结点或分支结点。一棵树的度是树内各结点的度的最大值。

分析如上图的一棵树，其中结点B的度为1，因为只有一条分支；结点B的度为2，因为有两个分支；结点F的度为3；结点G的度为0，所以结点G也叫叶子结点。对于这棵树，因为所有结点中度的最大值为结点F的度，所以树的度为3。

在树中，结点的子结点被称为该结点的孩子，相反，该结点被称为子结点的双亲。

同一个双亲的孩子之间被称为兄弟。

所以对于上面的数来说，结点D是结点G、H的双亲结点；结点G、H是结点D的孩子结点；结点G与结点H互称兄弟结点；那么对于结点B和结点A，它们是结点G、H的祖先结点。事实上，从根结点到该结点所经分支上的所有结点都称为该结点的祖先结点。那么相应地，结点G、H、D都被称为结点B的子孙结点。

树的其它概念

再来说一说关于树的一些其它概念。

结点的层次从根结点开始，根结点为第一层，那么根结点的孩子就处在第二层，我们知道，两个结点是同一个双亲，它们互称为兄弟结点；而不同双亲的两个结点，倘若它们的双亲处在同一层，则这两个结点互称为堂兄弟结点。比如还是上图的树中，结点D、E、F之间就互为堂兄弟结点。

树中结点的最大层次称为树的深度，也叫高度，例如上图的树的深度为4，因为有四层。

森林是m(m >= 0)棵互不相交的树的集合，这个放到后面说。

二叉树的定义

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

因为树的分支错综复杂，通常会将树转化为二叉树来进行运算，所以掌握好二叉树是很有必要的。
如下图的一棵二叉树：

满二叉树

满二叉树是一种特殊的二叉树，它特殊在哪呢？它特殊就在于一个满字，即一棵二叉树中的结点都存在，如下图就是一个满二叉树：

满二叉数的特点：

1. 每一层上的结点数都是最大结点数(即每层都满)
2. 叶子结点全部在最底层

完全二叉树

完全二叉树也是一种特殊的二叉树，定义如下：

深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。

比如下面的一棵二叉树，它是不是完全二叉树呢？

我们可以根据定义判断，先将其看做满二叉树按从上到下，从左到右进行编号：

可以看出，这棵二叉树的编号和满二叉树的编号完全一致，所以这是一棵完全二叉树，而下面这棵树就不是完全二叉树：

因为它的编号和这棵树的满二叉树状态的编号不同。

二叉树的性质

二叉树的性质共有五个，这些性质非常重要，在记忆这些性质的同时还应该对它们有一定的理解。

性质1

二叉树的性质1内容为：

在二叉树的第i层上至多有2^{i - 1}个结点(i ≥ 1)。

如下的一棵二叉树：

这样的一棵二叉树中，层数为3，当每个结点的度都为2时，这棵树的总结点数达到最多，所以上图中的结点树达到最大。其中第一层共有2^{1 - 1} = 1；第二层共有2^{2 - 1} = 2；第三层共有2^{3 - 1} = 4；由此得知性质1。

性质2

二叉树的性质2内容为：

深度为k的二叉树至多有2^k - 1个结点(k ≥ 1)。

通过二叉树的性质1，我们可以知道，对于深度为k的二叉树，其最大结点数为：2⁰ + 2¹ + ... + 2^{k - 1}。
由等比数列的公式可将上面的求和过程等价为：$$\frac{2^0 - 2^{k-1} * 2}{1 - 2} = \frac{1 - 2^k}{-1} = 2^k - 1$$

性质3

二叉树的性质3内容为：

对任何一棵二叉树T，如果其叶子数为n_o，度为2的结点数为n_₂，则n_o = n_₂ + 1。

比如下面的一棵二叉树：

度为2的结点有3个，3 + 1 = 4，所以叶子结点有四个，事实证明确实如此。

既然是度为2的结点数加1等于叶子结点数，我们就来看看结点的分支情况，假设一棵二叉树的总边数为B，则B = n - 1，为什么呢？
我们从树的底部往上看，对于每个孩子结点，都一定有一个双亲结点，也就是说，每个结点一定有一个分支，除了根节点，所以总边数为结点总数减1。
我们再从树的顶部往下看，对于度为2的结点，其有两条分支，对于度为1的结点，其有一条分支，所以总边数为：$$B = n_2 * 2 + n_1 * 1$$

综上所述，有如下等式成立：$$n - 1 = n_2 * 2 + n_1 * 1$$
得到如下等式：$$n = n_2 * 2 + n_1 * 1 + 1$$
又因为n为总结点数，所以总结点数等于度为2的结点数加度为1的结点数加叶子结点数，所以：$$n = n_2 + n_1 + n_0$$
这样又得到如下等式：$$n_2 * 2 + n_1 * 1 + 1 = n_2 + n_1 + n_0$$
等式进行化简，最终得到如下等式：$$n_0 = n_2 + 1$$

性质4

二叉树的性质4内容为：

具有n个结点的完全二叉树的深度为[log₂n] + 1。

[x]符号是一个求底的符号，表示求不大于x的最大整数。
比如下面的一棵完全二叉树：

其结点数为7，则其深度为[log₂7] + 1。
因为$$log_24 ≤ log_27 ≤ log_29$$
所以$$[log_27] = 2$$
从而求得这棵二叉树的深度为 2 + 1 = 3。

对于一棵完全二叉树的，假设其深度为k，其结点n有一个取值范围，当如下情况：

这棵完全二叉树的结点最小，根据性质2：
$$n = 2^{k - 1} + 1$$
因为倒数第二层的结点数为2^{k - 1}，则加1才能达到深度为k的完全二叉树的结点总数最小值。

而当如下情况，这棵完全二叉树的结点数达到最大：

此时根据性质2可得：$$n = 2^{k}$$

所以结点总数n的取值范围：$$2^{k - 1} < n ≤ 2^{k}$$
两边取对数，可得：$$k - 1 < log_2n ≤ k$$
因为深度k为整数，所以：$$k = [log_2n] + 1$$

性质5

二叉树的性质5内容为：
如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i(1 ≤i ≤ n)，则有以下关系：

1. 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲是结点[i / 2]
2. 如果2i > n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i
3. 如果2i + 1 > n，则结点i无右孩子；否则，其右孩子是结点2i + 1

需要注意的是性质4、性质5都是完全二叉树的性质。

二叉树的存储结构

本篇文章同样介绍二叉树的两种存储结构：

1. 顺序存储结构
2. 链式存储结构

二叉树的顺序存储结构

这里就可以解释为何要有完全二叉树的存在，比如下面的一棵二叉树：

我们知道顺序存储结构是通过数组实现的，那么该如何在数组中建立结点之间的相互关系呢？此时就需要借助完全二叉树实现，我们将其按照完全二叉树进行编号，如下图：

我们需要借助这些空结点来维护结点之间的关系，其在数组中的存储方式如下：

所以二叉树顺序存储结构的定义如下：

#define MAXSIZE 10

typedef int SqBiTree[MAXSIZE]

int main(){
   
   
    SqBiTree bt;
    return 0;
}

就是一个数组，没什么特别的，对二叉树的操作也就是对数组操作。

当二叉树中的结点间隔很大时，数组将会浪费大量的存储空间，而且顺序存储容量也不灵活，再加上顺序存储非常简单，所以这里不过多介绍顺序结构的实现。

二叉树的链式存储结构

接下来讲一讲二叉树的链式存储结构。
根据二叉树中的结点结构，我们可以定义如下类型：

#define TElemType int

typedef struct BiNode{
   
   
    TElemType data;    //数据域
    struct BiNode *lchild;    //左孩子指针
    struct BiNode *rchild;    //右孩子指针
}BiNode,*BiTree;

这样具有两个指针域的结点结构，我们称之为二叉链表，通常用于频繁操作孩子结点的场景中。
那么对于下面的一棵二叉树：

其二叉链表的存储方式如下：

而有些情况，我们需要频繁地去操作双亲结点，所以可以在结点结构中附加一个双亲结点，这样具有三个指针域的链表结构我们称之为三叉链表，结构定义如下：

#define TElemType int

typedef struct BiNode{
   
   
    TElemType data;    //数据域
    struct BiNode *lchild;    //左孩子指针
    struct BiNode *rchild;    //右孩子指针
    struct BiNode *parent;    //双亲指针
}BiNode,*BiTree;

而刚才的二叉树按照三叉链表的结构实现如下：

遍历二叉树

对二叉树的操作建立在遍历之上，所以我们需要掌握二叉树的各种遍历方式。
假设这样的一棵二叉树：

对这个二叉树的遍历有以下六种方式：

1. 123
2. 132
3. 213
4. 312
5. 231
6. 321

但其实这六种可以总结为三种，若规定只能从左到右遍历，则分为：

• 123——先序遍历
• 213——中序遍历
• 231——后续遍历

先序遍历

先序遍历即：先访问根结点，然后先序遍历左子树，最后先序遍历右子树，这是一个递归的过程。

比如下面的一棵二叉树：

按照先序遍历的规则，我们首先访问根结点，输出1；
然后先序遍历左子树，我们又对左子树进行同样的操作，先访问根结点，输出2，然后接着先序遍历其左子树，同样输出根结点4，因为结点4无孩子，所以返回上一层；
此时访问结点2的右子树，按照同样的方式，输出5；
以此类推，所以该二叉树的先序遍历结果为：1,2,4,5,3,6。

中序遍历

中序遍历即：先中序遍历左子树，然后访问根结点，最后中序遍历右子树，这是一个递归的过程。

这和先序遍历并无区别，只是访问根结点的顺序变了，如下的一棵二叉树：

我们首先中序遍历结点1的左子树；
对于结点2，同样中序遍历左子树；
对于结点4，因为其无孩子，所以无需遍历左子树，此时输出根结点4，也无需遍历右子树；
此时结点2的左子树遍历完毕，输出根结点2，然后中序遍历右子树；
因为结点5无孩子，所以直接输出根结点5；
此时结点1的左子树遍历完毕，输出根结点1，然后中序遍历右子树；
右子树以同样的方式遍历。
所以该二叉树的中序遍历结果为：4,2,5,1,3,6。

后序遍历

后序遍历即：先后序遍历左子树，然后后序遍历右子树，最后访问根结点，这是一个递归的过程。

还是这棵二叉树：

首先后续遍历结点1的左子树；
对于结点2，同样后序遍历左子树；
因为结点4无孩子，所以输出根结点4；
此时结点2的左子树遍历完毕，接着后序遍历右子树；
结点5无孩子，直接输出根结点5；
此时结点2的左右子树均遍历完毕，输出根结点2；
接着以同样的方式遍历结点1的右子树，最后输出根结点1即可。
所以该二叉树的后序遍历结果为：4,5,2,6,3,1。

由遍历结果确定二叉树

先序和中序序列确定二叉树

学习了二叉树的遍历之后，我们知道，对于一棵确定的二叉树，它有唯一的先序、中序和后序遍历的结果序列。
而要想通过结果序列反推出一棵二叉树，仅仅通过一种遍历方式的结果没有办法做到。
而事实上，只能由二叉树的先序序列和中序序列，或者由二叉树的后序序列和中序序列才可以确定一棵二叉树，其它序列的组合方式无法实现。

比如下面的一个例子：

1. 先序序列：A B C D E F G H I J
2. 中序序列：C D B F E A I H G J

因为先序遍历的方式是先访问根结点，所以通过先序遍历我们能够确定这棵二叉树的根是A；
又因为中序遍历的方式是先左子树，然后根结点，最后右子树，所以通过中序遍历我们能够知道，A的左边是左子树，A的右边是右子树，即：这棵二叉树的根结点的左孩子是C D B F E，右孩子是I H G J。

但是我们无法断定左右孩子具体是谁，所以我们还需要通过先序序列确定。
因为先序遍历先访问根结点，所以我们只需要找出在先序序列中C D B F E中哪个结点在最前面，很显然，B在最前面，所以根结点的左孩子是B。I H G J中G在最前面，所以根结点的右孩子是G。

我们继续通过中序序列确定结点B的左右孩子范围，B的左边有C D，B的右边有F E，再通过先序序列确定结点B的左右孩子，因为C在D的前面，所以C为结点B的左孩子，E在F前面，所以E为结点B的右孩子。

再看中序序列，C左边没有数据，所以C无左孩子，C右边为D，所以D为结点C的右孩子。
E左边为F，所以F为结点E的左孩子，E右边无数据，所以结点E无右孩子。

这样左子树就完成了，我们继续完成右子树，右子树就不一一分析了，方式是一样的，下面画出右子树：

中序和后序序列确定二叉树

关于中序和后序序列如何确定二叉树，实现方式和前者相同，我们可以通过后序知道二叉树的根结点，因为后序序列的遍历方式是最后访问根结点，所以后序序列的最后一个数据即为根结点，然后根据中序序列确定左右子树。

这也是为什么其它遍历序列无法确定二叉树的原因，因为无法确定根结点。