12 二叉树

• 0.1. 树的定义
• 0.2. 二叉树
  • 0.2.1. 存储二叉树
  • 0.2.1.1. 链式存储
  • 0.2.1.2. 顺序存储
  • 0.2.2. 遍历二叉树
  • 0.2.3. 二叉查找树
  • 0.2.3.1. 查找操作
  • 0.2.3.2. 插入操作
  • 0.2.3.3. 删除操作
  • 0.2.3.4. 其他操作
  • 0.2.3.5. 时间复杂度分析
  • 0.2.4. 支持重复数据的二叉查找树
  • 0.2.4.1. 插入操作
  • 0.2.4.2. 查找操作
  • 0.2.4.3. 删除操作
  • 0.2.5. 二叉查找树与散列表的对比
  • 0.2.5.1. 数据有序性
  • 0.2.5.2. 稳定性
  • 0.2.5.3. 执行效率
  • 0.2.5.4. 复杂度
  • 0.2.5.5. 存储空间利用率

树是一种非线性表结构比线性表的数据结构要复杂得多。

0.1. 树的定义

“树”中每个元素叫作“节点”；用来连线相邻节点之间的关系，叫作“父子关系”。

如下图所示：

1. A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。
2. B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。
3. 没有父节点的节点叫作根节点，如图中的节点 E。
4. 没有子节点的节点叫作叶节点，如图中的 G、H、I、J、K、L 都是叶子节点。

树还有三个比较相似的概念：

• 高度（Height）：节点到叶子节点的最长路径（边数），从下往上看，起点为0
• 深度（Depth）：根节点到这个节点所经历的边的个数，从上往下看，起点为0
• 层（Level）：节点深度+1，从上往下看，起点为1

树的高度：根节点的高度+1

0.2. 二叉树

二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

如上图所示：

• 编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。
• 编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

0.2.1. 存储二叉树

要理解完全二叉树定义的由来，需要先了解，如何表示（或者存储）一棵二叉树。想要存储一棵二叉树，有两种方法：

• 一种是基于指针的二叉链式存储法
• 一种是基于数组的顺序存储法

0.2.1.1. 链式存储

从图可以看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。

0.2.1.2. 顺序存储

基于数组的顺序存储法。

1. 把根节点存储在下标 i=1 的位置
2. 左子节点存储在下标 2*i=2 的位置
3. 右子节点存储在下标 2*i+1=3 的位置
4. 以此类推

所以，图中 D 节点的左子节点存储在 2*i=2*2=4 的位置，右子节点存储在 2*i+1=2*2+1=5 的位置。

如果节点 X 存储在数组中下标为 i 的位置：

• 下标为 2*i 的位置存储的就是左子节点
• 下标为 2*i+1 的位置存储的就是右子节点
• 下标为 i/2 的位置存储就是它的父节点

通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

如果是一棵完全二叉树只会浪费下标为0的存储位置，如果是一棵非完全二叉树会浪费较多存储空间。

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。堆其实就是一种完全二叉树，最常用的存储方式就是数组。

0.2.2. 遍历二叉树

如何将所有节点都遍历打印出来，经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

• 前序遍历：对于树中的任意节点，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历：对于树中的任意节点，先打印它的左子树，然后再打印它的右子树，最后打印它本身。

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

递归的关键是递推公式和终止条件，递推公式的关键是问题拆分，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。

# 前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

# 中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

# 后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

# 伪代码
void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

二叉树遍历的时间复杂度是O(n)。

0.2.3. 二叉查找树

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树，是为了实现快速查找而生的。它还支持快速插入、删除一个数据。这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

0.2.3.1. 查找操作

1. 先取根节点，如果它等于我们要查找的数据，那就返回
2. 如果要查找的数据比根节点的值小，那就在左子树中递归查找
3. 如果要查找的数据比根节点的值大，那就在右子树中递归查找

0.2.3.2. 插入操作

插入过程有点类似查找操作。

1. 新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系
2. 如果要插入的数据比节点的数据大
   1. 如果节点的右子树为空，就将新数据直接插到右子节点的位置
   2. 如果节点的右子树不为空，就再递归遍历右子树，查找插入位置
3. 如果要插入的数据比节点数值小
   1. 如果节点的左子树为空，就将新数据插入到左子节点的位置
   2. 如果不为空，就再递归遍历左子树，查找插入位置

0.2.3.3. 删除操作

删除操作就比较复杂。针对要删除节点的子节点个数的不同，分三种情况来处理：

1. 第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。
2. 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
3. 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。

0.2.3.4. 其他操作

二叉查找树中快速地查找最大节点和最小节点、前驱节点和后继节点。

中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

0.2.3.5. 时间复杂度分析

图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。

大部分情况下，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。将高度转为层数，第 K 层包含的节点个数就是 2^(K-1)。最后一层的节点个数在 1 个到 2^(L-1) 个之间（假设最大层数是 L）。

所以得到如下公式：

n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式，可以计算出，L 的范围是[log2(n+1), log2n +1]。

需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是平衡二叉查找树。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

0.2.4. 支持重复数据的二叉查找树

在实际的软件开发中，二叉查找树中存储的，是一个包含很多字段的对象。利用对象的某个字段作为键值（key）来构建二叉查找树，把对象中的其他字段叫作卫星数据。

0.2.4.1. 插入操作

如果存储的两个对象键值相同，有两种解决方法：

1. 第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
2. 第二种方法比较不好理解，不过更加优雅。每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，就将这个要插入的数据放到这个节点的右子树，即把这个新插入的数据当作大于这个节点的值来处理。

0.2.4.2. 查找操作

当要查找数据的时候，遇到值相同的节点，并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

0.2.4.3. 删除操作

对于删除操作，需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

0.2.5. 二叉查找树与散列表的对比

• 散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效
• 二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)

0.2.5.1. 数据有序性

• 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序
• 二叉查找树只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列

0.2.5.2. 稳定性

• 散列表扩容耗时很多，当遇到散列冲突时，性能不稳定
• 二叉查找树的性能不稳定，但在工程中最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)

0.2.5.3. 执行效率

• 散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快
• 加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高
  

0.2.5.4. 复杂度

散列表的构造比二叉查找树要复杂，需要考虑的东西很多，比如：

• 散列函数的设计
• 冲突解决办法
• 扩容
• 缩容

平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

0.2.5.5. 存储空间利用率

为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。在实际的开发过程中，需要结合具体的需求来选择使用哪一个。