前言

在上篇文章中，向大家介绍了线性数据结构中的栈、队列和串三种数据结构， 相对来说比较简单，栈的特点是先进后出(FILO)，队列的特点是先进先出(FIFO)。栈包含入栈和出栈两个操作，两个操作操作的都是栈顶元素；队列包含入队和出队两个操作，元素从队尾进入队列，需要时从队头取出元素。

全文大约【4500】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考...

一. 树的简介

1. 概念

树(Tree) 是非线性结构的典型代表。在树型数据结构中，数据元素之间存在一对多的关系。在数据结构中，对树的定义是：树是由n(n>0)个有限结点组成一个具有层次关系的集合。当n=0时，称为空树。

之所以把这些由层次关系的结点集合称之为树，主要是因为其在形状上看起来特别像一棵倒挂的树，即树根朝上，树叶朝下。首先壹哥给出树结构所具备的特点：

(1). 树有且仅有一个特定的根(Root)结点。

(2). 除了根结点，其余每个结点都有且只有一个直接前驱，这个前驱结点叫父结点.

(3). 树的每个结点都可以有多个后继，叫做子结点。没有后继的结点称为叶子结点。有父结点，也有子结点，这样的结点被称为中间结点或分支结点。

(4). 除了根结点，其余结点可分为m(m>0)个互不相交的有限集合。其中每一个集合本身又是一棵树，称为子树。

但是，如果产生子树相交的情况，就不符合树结构的定义，也就不属于树了。比如下图：

如上两图所示，左图中②和③有相交，右图中结点②和节点③均与节点⑤相连，这两种情况下都不能称之为树。

2. 基本术语

2.1 树的高度和深度

树的最大层级数，被称为树的高度或深度。我们通过图例说明如下：

如上图所示，该树的高度是4，深度为4。根结点在第1层，结点8、9、10位于第4层。

备注：托马斯·科尔曼等人所著的《算法导论》一书中，树的高度是从“0”开始计数的，在本篇文章中，我们遵照惯例，树的高度是从“1”开始计数。

2.2 结点关系

具有同一父结点的结点互相称为兄弟结点。比如，上文图例所示中：结点2和3，结点4和5，结点6和7，结点8和9彼此是兄弟结点。

2.3 树的度数

特别的，我们把：一个结点的子结点的个数称为该结点的度数。度为0的结点就是叶子结点，而度不为0的结点就是分支结点。同时，我们还规定：一棵树的度指的是该树中结点的最大度数。比如，上文所示图例中：结点2、3、4的度为2，结点6的度为1，结点5、7、8、9、10的度为0。这棵树的度为2。

3. 树的分类

根据度的大小，我们可以将树可以分为二叉树和多路树。堆也属于一种多路树结构，另外根据度的大小，堆也分为二叉堆和多叉堆。具体的逻辑关系如下图所示：

在如上的示例图中，给出了树型数据结构所涉及的常见的分类种类，在后续的文章中，我们会逐渐学习到，大家稍安勿躁，接下来让我们先从二叉树开始学起。

二. 二叉树

1. 概念

二叉树(Binary Tree) 是树的一种常见形式。二叉树的任意结点最多可以有两个子结点，也可以只有一个或者没有子结点。因此二叉树的度数一定小于等于2。二叉树结点的两个子结点，一个被称为左子结点，一个被称为右子结点。二叉树严格区分左右子结点，两个子结点的顺序是固定的，即使只有一棵子树也要区分左右。

如果我们把二叉树继续进行分类，就会衍生出满二叉树和完全二叉树。

• 满二叉树：满二叉树是一种理想状态。二叉树的所有非叶子结点都存在左右子结点，每个非叶子结点的度都是2，并且所有叶子结点都在同一层上，那么这个树就是满二叉树。

如上图所示： 左图中，所有非叶子结点都存在左右子结点，每个非叶子结点的度都是2，同时所有叶子结点均在同一层，符合满二叉树的定义，所以左图是满二叉树。右图中，虽然每个非叶子结点都有左右子结点，且每个非叶子结点的度都是2，但所有叶子结点并不在同一层，因此不属于满二叉树。由此，我们 可以知道，判断一棵二叉树是否是满二叉树，有三个条件：

• 每个非叶子结点都存在左右2个子结点
• 每个非叶子结点的度都是2
• 所有叶子结点均在同一层

以上三个条件，实际前两个条件描述的是同一回事。

• 完全二叉树：如果二叉树中除去最后一层结点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

如上图所示，结合完全二叉树的定义，可以知道完全二叉树需要满足两个条件：

• 除最后一层外为满二叉树；
• 最后一层的结点依次从左至右，中间不能有缺失。

2. 性质

二叉树的性质，也是二叉树有关的一些结论，所谓结论，就是指这些设计到二叉树相关的特性的内容，可以直接作为结果或者结论进行引用。我们依然分类进行描述：

2.1 普通二叉树的性质

• 第i层最多可以有2 i-1 个结点：根据结论，我们可以验证二叉树第1层最多有1个结点，第2层最多有2个结点，第3层最多有4个结点，依次类推。当然，需要注意的是，此处说的是最多，并不是一定会有，要区分清楚。
• 若二叉树深度为k，则二叉树最多有2 k -1个结点：该结论也可以通过举例验证，二叉树的深度为1时，结点最多就1个；深度为2时，结点最多有3个；深度为3时，结点最多为7个。依次类推，均符合该结论公式。
• 若叶子结点数为n0，度为2的结点数为n2，则n0=n2+1：该结论也可以用另外一句话表述，即叶子结点数比度为2的结点多1个。

2.2 满二叉树的性质

满二叉树是特殊的二叉树，因此所有的普通二叉树的性质满二叉树都满足。除此之外，满二叉树特有的性质有：

• 满二叉树中第i层一定有2 i-1 个结点。
• 深度为k的满二叉树一定有2 k -1个结点，且一定有2 k-1 个叶子结点。
• 具有n个结点的满二叉树的深度为log 2 (n+1) 。

2.3 完全二叉树的性质

如上图所展示的是一棵完全二叉树，为了方便区分该二叉树的每一个结点，我们其将含有的结点按照层次从左到右依次标号，依次为1-11。若根据该规则，则对于任意一个结点i，完全二叉树具有以下结论：

• 若i>1，则i结点的父结点的编号是i/2(向下取整) 。比如：i=5结点，其父结点编号为2，满足结论。
• 若2i>n(n为总结点的个数)，则结点i肯定没有左叶子结点，否则其左子结点是结点2i。
• 若2i+1>n，则结点i肯定没有右子结点；否则右子结点是结点2i+1。
• 完全二叉树只能有0个或1个度为1的结点，叶子结点数比度为2的结点数多1个。

总结： 对于普通二叉树，满二叉树，以及完全二叉树的特点和其所具有的性质，在使用时最简单的方式是通过画图例的方式进行验证，当然如果我们能把上文中列出的所有性质公式都记住自然是最好的。

3. 二叉树的存储

在前面的文章中，我们已经学习过数组和链表，此处刚好可以使用这种结构对二叉树的结点进行存储。因此，二叉树的存储一共有两种方式，分别是：顺序存储、链式存储。

3.1 顺序存储(数组)

所谓的顺序存储，指的是使用数组存储的二叉树。

我们在使用数组存储时，会按照层级顺序把二叉树的结点放到数组中对应的位置上。如果某一个结点的左子结点或右子结点空缺，则数组的相应位置也要空出来。对于一个稀疏的二叉树(子结点不满)来说，用顺序存储是非常浪费空间的。所以二叉树的顺序存储一般只适用于完全二叉树，或者说完全二叉树才适合使用顺序表存储。当顺序存储普通二叉树时，需要提前将普通二叉树转化为完全二叉树。

如上图所示，给定的二叉树是一棵普通的二叉树。若使用数组进行存储，首先需要将该二叉树补充调整为一棵完全二叉树如上右图所示，需要添加的两个结点使用虚线表示（不存储具体数据，空余），然后再使用数组存储该完全二叉树。可以看到，上图的数组中，下标4和下标5位置空余，原因是两位位置恰好对应的是补充的两个结点。

由此，我们也能进一步理解：若使用数组存储普通二叉树，往往会浪费存储空间。

3.2 二叉树链式存储(链表)

我们推荐大家使用链表对二叉树进行存储。链式存储二叉树，其结点结构与双向循环链表一致，每一个结点包含三个部分：存储数据的data变量、指向左子结点的left指针、指向右子结点的right指针，这样的链表称为二叉链表。如下图所示：

三. 遍历操作

在前面的文章中，我们已经介绍过数组的遍历和链表的遍历。所谓遍历就是按照某种逻辑规则，依次访问集合的每个元素的操作。对于二叉树，同样可以按照某种逻辑依次访问二叉树的每一个结点。二叉树的遍历可以分为两大类：深度优先遍历、广度优先遍历。

1. 深度优先遍历

所谓深度优先( depth first search，DFS ) ，顾名思义就是偏向于纵深，“一头扎到底”的访问方式。深度优先遍历又根据遍历顺序的不同分为三种：前序遍历、中序遍历、后序遍历。

1.1 前序遍历

所谓前序遍历，是指二叉树遍历每个子树的时候，都是按照根结点、左子树、右子树的顺序来遍历，因为根结点在前，所以叫做前序遍历。前序遍历中根结点的优先级别最高。如下图所示：

如上图所示：

• 先访问第一层，第一次只有一个结点，可以得到A结点。
• 再访问第二层，第二层中B是A的左子树，而B又是第三层D和E的父结点，因此要先访问B结点。
• 访问B后，再访问B的下一层即第三层。在第三层中，B的左子树D，又包含一个右子树G，因此，对于D和G来说，应该先访问D。因此访问D结点。
• 访问D后，访问下一层即第四层，D只有一个右子树G，因此访问G结点。
• G结点访问结束后，意味着D和G组成的这课分支子树就结束了，进一步访问BDE这三个结点组成的分支子树。因为B和D已经被访问过了，所以访问E结点。
• 访问E后，BDE组成的分支子树已经遍历结束，继续遍历ABC结点组成的子树，由于A和B已经被访问，因此访问C结点。
• 依次类推，和左侧访问规则一样，继续访问得到F结点和H结点。

1.2 中序遍历

如果二叉树遍历每个子树的时候，都是按照左子树、根结点、右子树的顺序来遍历，因为根结点在中间，所以叫做中序遍历。如下图所示：

如上图所示，虚线箭头和数字就是按照中序遍历的规则对二叉树进行遍历的步骤，最后可得到中序遍历顺序：D G B E A C H F。通过上面二叉树的图示和结果，我们还可以发现一个中序遍历的规律：第一个元素是树结构中最左侧的元素，最后一个是树结构中最右侧的元素，根结点在中间位置输出。

1.3 后序遍历

二叉树遍历每个子树的时候，都是按照左子树、右子树、根结点的顺序来遍历，因为根结点在最后，所以叫做后序遍历。如下图所示：

如上图所示，虚线箭头和数字表示除了二叉树的后续遍历的步骤。我们发现出规律：后序遍历第一个输出的元素是根结点左侧最底层第一个元素，最后一个输出的是根结点元素。

2. 广度优先遍历

广度优先遍历( Breadth First Search，BFS )也叫层序遍历，就是按照二叉树中的层次从左到右依次遍历每层中的结点。层序遍历的实现思路是利用队列来实现。先将树的根结点入队，然后再让队列中的结点出队。队列中每一个结点出队的时候，都要将该结点的左子结点和右子结点入队。当队列中的所有结点都出队，树中的所有结点也就遍历完成。此时队列中结点的出队顺序就是层次遍历的最终结果。如下图所示：

如上图所示，广度优先遍历比较容易理解，从上到下按层依次对二叉树的结点进行遍历，最后可得到遍历结果。

四. 结语

通过本篇内容，带大家开始学习树型数据结构，在实际应用中，二叉树又是使用最广泛的，特别是二叉树的几种遍历操作的规则，需要做着重掌握。在面试或应试考试中，通常会根据前序、中序、后序中的两种序列，询问另外一种树的遍历结果，大家要重点关注。