LV010-二叉树简介

一、二叉树简介

1. 什么是二叉树

什么是二叉树，二叉树也是一种树形结构，它是一种特殊的树，它有以下特点：

（1）二叉树是有序树，严格区分左孩子和右孩子，即使只有一个子节点也要区分左右；

（2）树中包含的各个结点的度不能超过 2 ，只能是 0 、 1 或者 2 。

2. 形态

二叉树的形态一共可以有五种：

3. 性质

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

【证明】数学归纳法：

1. i = 1 时，只有一个根节点，显然 $2^0=1$，上述结论成立；
2. 假设对所有的 j ，1 ≤ i ＜j 时上述结论成立，即在第 j 层上至多有 $2^{j-1}$ 个结点；
3. 所以在第 i - 1 层上至多有 $2^{i-2}$ 个结点，由于二叉树的每个结点的度数至多为 2 ，所以在第 i 层上结点最多为 i - 1 层上结点数的两倍，即第 i 层上结点数至多为 $2^{i-1}$。

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

【证明】

由性质（1）可知，二叉树第 i 层上至多有 $2^{i-1}$ 个结点，一共有 k 层，所以总的结点数 n 为：

$n=2^0+2^1+......+2^{k-1}$

等比数列求和公式为：$S_n=\frac{a_1-a_{n}q)}{1-q}$

所以 $ n = \frac{1-2^{k-1}*2}{1-2} = 2^k-1$

（3）对任意的二叉树 T ，若其叶子结点数为 $n_0$，度数为 2 的结点数为 $n_2$，则 $n_0=n_2+1$。

【证明】

设 $n_1$ 为二叉树 T 中度数为 1 的结点数，n 为二叉树的总结点数，则 $n=n_0+n_1+n_2$

对于每一个结点来说都是由结点的父结点分支表示的，假设二叉树中树的分支数为 B ，那么总结点数 $n=B+1$

而二叉树的分支数 $B=n_1+2\ast n_2$，所以有 $n=n_1+2\ast n_2+1$

所以 $n = n_1 + 2*n_2 + 1 = n_0 + n_1 + n_2 $

两边消去 $n_1$ 可以得到 $n_0=n_2+1$。

3. 分类

3.1 满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2 ，则此二叉树称为满二叉树。

满二叉树除上述三条一般二叉树的性质之外，还有如下性质：

（1）满二叉树的第 i (i ≥ 1) 层上有 $2^{i-1}$ 个结点。

（2）深度为 k (k ≥ 1) 的满二叉树有 $2^k-1$ 个结点，叶子数为 $2^{k-1}$。

（3）满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。

（4）具有 n 个节点的满二叉树的深度为 ${\log }_2(n+1)$。

3.2 完全二叉树

只有最下面一层有度数小于 2 的节点，且最下面一层的叶节点集中在最左边的若干位置上的二叉树。也就是说完全二叉树去除最下边一层的所有节点后是一个满二叉树。

完全二叉树除上述三条一般二叉树的性质之外，还有如下性质：

对于任意一个含有 n 个结点的完全二叉树来说，如果将含有的结点按照层次从左到右依次标号，如上图所示，根节点为 1 号节点，则对任意一个结点 i 有：

（1）当 i ＞ 1 时，结点 i 有父结点，且编号为 i / 2 。

（2）当 2i ≤ n 时，有左孩子，且左孩子编号为 2i ；当 2i > n 时，结点肯定没有左孩子，节点本身为叶子结点。

（3）当 2i + 1 ≤ n 时，有右孩子，且右孩子编号为 2i + 1 ；当 2i + 1 > n 时，结点肯定没有右孩子。

（4）当 i 为奇数且不为 1 时，结点 i 有左兄弟，左兄弟编号为 i - 1 ，否则 i 没有左兄弟。

（5）当 i 为偶数且小于 n 时，结点 i 有右兄弟，右兄弟编号为 i + 1 ，否则 i 没有右兄弟。

二、存储结构

我们前边学的有顺序存储结构和链式存储结构，他们都可以作为二叉树的存储结构。

1. 顺序存储结构

使用顺序表（数组）存储二叉树，这叫做二叉树的顺序存储，但是要注意的就是，顺序存储只适用于完全二叉树。如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

那普通二叉树如何转化为完全二叉树呢？如下图所示：

这样一来，二叉树就都可以满足顺序存储的条件了，那怎么存储呢？如下图所示：

通过顺序表存储的二叉树，可以很轻松还原，但是顺序存储结构是特别浪费空间的，那些为了转化为完全二叉树而补充出来的结点并没有什么实际用处，反而还浪费了很大的空间，比如上图中，原本结点只有三个，但是存储的时候却至少需要多出来三个结点的空间。

2. 链式存储结构

我们还可以通过链表来存放二叉树，存储方式如下：

存放结点的链式节点结构有三部分组成：

• Lchild ：指针域，指向存放左孩结点的链表节点的指针。
• data ：数据域，结点存放的数据。
• Rchild ：指针域，指向存放右孩结点的链表节点的指针。

三、二叉树遍历

1. 遍历算法的由来

对于一个二叉树，在我们不知道有哪些遍历算法的情况下，很容易我们会想到一种，就是按层次，从上到下，每一层次从左到右来遍历，这种遍历的方式被称之为层次遍历。

那还有其他的遍历方法吗？还有一种就是我们遵循从上到下，从左到右的遍历方式，如下图所示：

这样依然可以访问到所有的结点，他们的区别是什么呢？层次遍历中，每次只经过结点一次，而下边这种遍历，对于结点 B 来说，遍历的时候经过了它三次，即便是叶子结点，看上去是两次，但是也可以看做是三次。我们可以在经过这个结点不同的时机进行访问，如此便有三种访问方式了：

• 遇到一个结点，先访问，再遍历左右子树，称之为 先序遍历。
• 遇到一个结点，第一次先不访问，先访问它的左子树，再访问这个结点，最后访问右子树，称之为 中序遍历。
• 遇到一个结点，第一次不访问，先访问左子树，第二次还是不访问，然后访问右子树，最后访问这个结点，称之为 后序遍历。

2. 遍历过程

2.1 层次遍历

层次遍历过程如下图所示：

2.2 先序遍历

先序遍历过程如下图所示：

2.3 中序遍历

中序遍历过程如下图所示：

2.4 后序遍历

后序遍历过程如下图所示：