【数据结构】二叉树：简约和复杂的交织之美

专栏引入：

哈喽大家好，我是野生的编程萌新，首先感谢大家的观看。数据结构的学习者大多有这样的想法：数据结构很重要，一定要学好，但数据结构比较抽象，有些算法理解起来很困难，学的很累。我想让大家知道的是：数据结构非常有趣，很多算法是智慧的结晶，我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏，在这里我将把数据结构内容以有趣易懂的方式展现给大家。

1.二叉树

生活中，我们经常会遇到管理大量数据的情况，比如图书馆书记的分类。而二叉树这种数据结构正是用来解决这种问题的，当我们阅读书时，书中的每个条目都有专门分类和子分类，为了更好的组织这些内容，需要使用一种高效的数据结构来存储和访问信息。下面举个简单的例子来引入二叉树，我们在中学学习生物时知道了植物主要分为：种子植物、苔藓植物等。那它们是如何进行分类的呢？我们看下面这张图片：

通过这种方式，我们可以逐级展开二叉树，更详细的组织植物分类的信息，每个节点都代表一个特定的分类，而子节点则代表该分类的下一级分类。这样我们可以更加轻松的查找和比较不同的植物分类信息。下面我们就来揭开二叉树的神秘面纱。

1.1二叉树的定义

二叉树是n（n>=0）个节点的有限集合，该集合或者为空集合（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。在下面的图中，左边的就是一棵二叉树，而右边的因为它的F节点有3个子节点，所以它不是二叉树。

1.2二叉树的特点

二叉树具有以下几个特点：

每个节点最多有两个子节点，所以二叉树中不存在度大于2的节点。注意不是一定要有两个节点，而是最多有两个节点，没有节点或者只有一个节点也是可以滴。
左子树和右子树是有顺序的，次序不能颠倒，因此二叉树是有序树。
即使结构中某节点只有一个子节点，也要区分它是左节点还是右节点。

二叉树具有以下五种基本形态：空二叉树、只有一个根节点、根节点只有左子树、根节点只有右子树、根节点既有左子树又有右子树。

1.3特殊的二叉树

1.3.1斜树

斜树，顾名思义，斜树一定是斜的，但是向哪里斜还是有讲究的。所有节点都只有左子树的二叉树的叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树，这两者统称为斜树。在上一张图中根节点只有左子树和根节点只有右子树就是左斜树和右斜树的一个简单例子。斜树也有很明显的特点，就是每一层只有一个节点，节点个数和二叉树的深度相同。肯定也有人好奇：这也叫树？这不和线性表一样吗？确实，线性表可以理解成树的一种极其特殊的表现形式。

1.3.2满二叉树

我们通常举例子都是参差不齐的二叉树，那是否存在完美的二叉树呢？我们看下面这张图片：

看来完美的二叉树是存在的。在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在一层上，这样的二叉树叫做满二叉树。下面就是一个满二叉树，从样子上看就感觉它很完美：

单是每一个节点都存在左右子树，不能算满二叉树，还必须要所有叶子都在一层上，这样才能做到整棵树的平衡。因此，满二叉树的特点有：

叶子只能出现在最底层，出现在其他层就不能达到平衡状态。
除了叶子节点外，每个节点都有两个子节点。即所有非叶子节点的度都为2.
在同样深度的二叉树中，满二叉树的节点个数最多，叶子数最多。

满二叉树的每一层都是满的，没有任何缺失节点。由于每个节点都具有两个子节点，满二叉树的平衡性很好。这使得在满二叉树上执行搜索、插入和删除等操作的平均时间复杂度非常高效。在满二叉树中，从根节点到任意一个叶子节点的路径长度都相同，是最短的路径。满二叉树常用于堆数据结构。满二叉树在实际应用中比较少见，因为它要求节点数必须是2的幂次方，而真实的数据往往不具备这样的特点。

1.3.3完全二叉树

对一棵具有n个节点的二叉树进行层序编号，如果编号为i（1≤i≤n）的节点与同样深度的满二叉树中的编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。如下图：

在理解时，我们要注意区分满二叉树和完全二叉树。首先，从字面上区分，“完全”和“满”的区别，满二叉树一定是一棵完全二叉树，完全二叉树不一定是满的。其次，完全二叉树的所有节点和同样深度的满二叉树，它们按层序编号相同的节点，是一一对应的，这个关键词是按层序编号。像下面的二叉树中，因为5节点没有右子树，只有左子树，使得按层序编号的第11个编号空档了，它不是完全二叉树：

只有下面图中的树，尽管它不是满二叉树，但编号是连续的，所以它是完全二叉树：

这里我们就可以总结出完全二叉树的一些特点：

叶子节点只能出现在最后两层。
最下层的叶子节点一定是集中在左部连续位置。
倒数第二层，如果有叶子节点，一定都在右部连续位置。
如果节点的度为1，则该节点只有左孩子，及不存在右子树的情况。
同样节点数的二叉树，完全二叉树的深度最小。

通过上面的理解，我们也知道了一个判断二叉树是否是完全二叉树的方法：那就是看树的示意图，给每个节点按照满二叉树的结构逐层顺序编号，如果编号出现空挡，就说明不是完全二叉树，反之就是。完全二叉树在实际应用中较为常见，它具有以下的优点：

节点的存储更加高效：由于完全二叉树的特点，可以使用数组来存储节点。这样可以大大节省存储空间，因为不需要为每个节点额外存储左右子节点的指针。
访问效率更高：由于节点的存储更加高效，可以使用数组的索引来访问节点。这样可以实现随机访问，访问的时间复杂度是O(1)。而在其他类型的二叉树中，如果要找到某个节点，需要从根节点出发进行遍历，访问的时间复杂度较高。

1.4二叉树的性质

1.4.1二叉树的性质1

在二叉树的第i层至多有 $2^{i-1}$ 个节点（i≥1）。这个性质很容易理解，我们观察一下满二叉树：

第一层是根节点，只有一个，所以 $2^{0}$ =1。第二层有两个， $2^{1}$ =2。第三层有四个， $2^{2}$ =4。第四层有八个， $2^{3}$ =8。通过数据归纳法的论证，我们可以很轻松的得出在二叉树的第i层上至多有 $2^{i-1}$ 个节点（i≥1）的结论。这个性质的重要性在于它给出了二叉树的每一层上节点数量的上限。通过这个性质，我们可以更好地理解和分析二叉树的结构。同时，这个性质也为二叉树的遍历、搜索等操作提供了重要的依据和限制。

1.4.2二叉树的性质2

深度为k的二叉树至多有 $2^{k}-1$ 个节点（k≥1）。这里一定要注意，是 $2^{k}$ 后再减1，而不是 $2^{k-1}$ 。如果不注意的话很容易和性质1搞混。深度为k也就是有k层的二叉树，我们接着以上面那个满二叉树为例来看：如果只有一层，至多有 $2^{1}-1=1$ 个节点。如果只有两层，至多有 $2^{2}-1=1+2$ 个节点。如果只有三层，至多有 $2^{3}-1=1+2+4$ 个节点。如果只有四层，至多有 $2^{4}-1=1+2+4+8$ 个节点通过数据归纳法，我们可以得出：二叉树的深度为k层，此二叉树至多有 $2^{k}-1$ 个节点。

1.4.3二叉树的性质3

对于任何一棵二叉树，如果其终端节点数为 $n_{0}$ ，度为2的节点数为 $n_{2}$ ，则 $n_{0}=n_{2}+1$ 。这是一个非常重要的性质，首先我们从二叉树的构建过程一步一步来理解它：

首先，我们先看只有一个根节点的时候，度为0的节点个数n0=1，度为2的节点的个数为n2=0。我们设度为1的节点的个数为n1，接着，我们给根节点加一个节点，这时候一定会减少一个度为0的节点（一个度为0的节点变为度为1的节点），然后再加一个度为0的节点（新增的节点因为没有子节点，所以增加一个度为0的节点），度为0的节点个数变化之后和之前的个数一样，所以n0仍为1，n2仍为0。然后，我们再加一个节点，这时候会减少一个度为1的节点，然后增加一个度为0的节点和一个度为2的节点（度为1的节点变来）。通过这个规律我们可以发现度为0的节点比度为2的节点多1个，即n0=n2+1。

同时我们也可以发现树节点的总数为n=n0+n1+n2。通过下图的例子，节点总数为10，它是由A、B、C、D度为2的节点，F、G、H、I、J度为0的叶子节点和E这个度为1的节点组成的。总和为4+1+5=10。

因为这个性质很重要，刷题时会经常出现考察这个性质的题，我从网上找了两个试题来帮助大家对这个性质加深印象：

1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为

（）
A 不存在这样的二叉树

B 200
C 198
D 199
答案：C

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（）

A n
B n+1
C n-1
D n/2

答案：A

解析：根据题意，我们可以知道：n0+n1+n2=2n，n0=n2+1，所以n0+n1+n0-1=2n，即 2n0+n1-1=2n我们在接着分析这棵树是一个完全二叉树，所以度为1的节点个数为0或 1，因为n0、n1、n2的值为整数，所以我们可以得出n1为1，然后解开这个方程就知道n0的值为n，即叶子节点个数为n。

1.4.4二叉树的性质4

具有n个节点的完全二叉树的深度h=| $\log_{2}n$ |+1（这里的 |x| 表示不大于x的最大整数）。由满二叉树的定义我们可以知道，深度为h的满二叉树的节点数n一定为 $2^{h}-1$ ，因为这是最多的节点个数。那么对于n= $2^{h}-1$ 倒推可以得到满二叉树的深度为h= $\log (n+1)$ ，完全二叉树我们前面也提到过，它是一棵具有n个节点的二叉树，如果按照层序编号后与同样深度的满二叉树中编号节点在二叉树中的位置完全相同，那他就是完全二叉树，也就是说，它的叶子节点只会出现在最下面两层，它的节点数一定小于等于同等深度的满二叉树的节点数 $2^{h}-1$ ，但一定多于 $2^{h-1}-1$ ，即满足 $2^{h-1}-1<h\leqslant 2^{h}-1$ ，由于节点数n是整数， $n\leq 2^{h}-1$ 意味着 $n< 2^{h}$ ， $n>2 ^{h-1}-1$ 意味着 $n\geq 2^{k-1}$ ，所以 $2^{h-1}\leq n< 2^{h}$ ，不等式两边取对数，得到 $h-1\leq \log_{2}n< h$ ，而h作为深度也是整数，因此h=| $\log_{2}n$ |+1。