Skip to content

树

二叉树

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子树，分别称为左子树和右子树。常见的结构体定义如下： 

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
};

常见的遍历二叉树的方式有三种：前序遍历（pre-order traversal）、中序遍历（in-order traversal）和后序遍历（post-order traversal）。前序遍历的顺序是访问当前节点，然后访问左子树，最后访问右子树；中序遍历的顺序是访问左子树，然后访问当前节点，最后访问右子树；后序遍历的顺序是访问左子树，然后访问右子树，最后访问当前节点。

二叉搜索树

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点都满足以下条件：

  • 左子树中的所有节点的值都小于该节点的值。
  • 右子树中的所有节点的值都大于该节点的值。

二叉搜索树支持以下操作：

  • 搜索（Search）：对于给定的键 key，在二叉搜索树中查找是否存在一个节点的键值等于 key。如果找到返回对象，否则报告没有找到。
  • 最大/最小（Max/Min）：返回二叉搜索树中键值最大的节点或最小的节点。
  • 前驱/后继（Predecessor/Successor）：对于给定的节点 x，返回二叉搜索树中键值小于 x 的最大节点（前驱）或键值大于 x 的最小节点（后继）。
  • 按序输出（Output sorted）：按照键值大小依次输出所有节点。
  • 选择（Select）：对于给定的整数 i，返回二叉搜索树中第 i 小的节点。
  • 秩（Rank）：对于给定的键值 key，返回二叉搜索树中键值小于等于 key 的节点的数量。
  • 插入（Insert）：将一个新的节点插入到二叉搜索树中。
  • 删除（Delete）：从二叉搜索树中删除一个节点，其键值等于给定的 key。

上述操作除了按序输出以外，其他操作的时间复杂度是 ，其中 是二叉搜索树的高度。在最坏情况下，二叉搜索树可能退化成一个链表，此时高度为 ，时间复杂度为 。在平均情况下，二叉搜索树的高度为正比于 ，因此平均时间复杂度为 。按序输出的时间复杂度是 。

搜索的实现与二分查找算法类似，首先比较 key 与当前节点的键值，如果相等则返回当前节点；如果 key 小于当前节点的键值，则继续在左子树中搜索；如果 key 大于当前节点的键值，则继续在右子树中搜索。如果搜索到一个空节点，则说明没有找到 key。

最小节点是二叉搜索树中键值最小的节点，实现就是一直向左子树遍历，直到找到一个没有左子树的节点。最大节点恰好相反。

前继是比给定节点的键值小的最大节点，如果给定节点有左子树，则前继是左子树中的最大节点；如果给定节点没有左子树，则前继是从根节点开始向下遍历，最后一个比给定节点小的节点。也就是说，当向上开始往左转时，父节点是前继，假定 y 是 z 的右节点，那么返回 z。后继的实现与前继相反。

有序输出的一种实现是首先调用 Min 获取最小节点，然后不断调用 Successor 获取下一个节点，直到没有后继为止。不过这种实现的时间复杂度是 ，因为每次调用 Successor 的时间复杂度是 。更高效的实现是使用中序遍历（in-order traversal），在中序遍历过程中访问每个节点时输出它的键值，这样时间复杂度是 。

插入操作和搜索有点类似，从根节点开始比较要插入的 value 与当前节点的键值，如果 value 小于当前节点的键值，则继续在左子树中插入；如果 value 大于当前节点的键值，则继续在右子树中插入；如果相等则不插入（或者根据需求更新节点）。当找到一个空节点时，将新节点插入到该位置。这里需要注意，要根据最后一次比较的结果来确定新节点是父节点的左子树还是右子树。

对大部分的数据结构而言，删除操作通常比较复杂。主要挑战是在删除一个节点之后要保持二叉搜索树的性质。下面分三种情况讨论。第一种情况最简单，要删除的节点没有子节点，直接删除即可。第二种情况，要删除的节点有一个子节点，将要删除的节点的父节点直接连接到要删除的节点的子节点上，然后删除要删除的节点。假定要删除的节点是 x，父节点是 y，子节点是 z，如果 x 是 y 的左子树，那么将 y 的左子树指向 z；如果 x 是 y 的右子树，那么将 y 的右子树指向 z。第三种情况，要删除的节点有两个子节点，这样就比较麻烦，没有明显的方式来确定要删除的节点的父节点应该连接到哪个子节点上。解决这个问题的方法是找到要删除节点 x 的前继节点 y，然后交换两个节点。x 的前继节点 y 肯定没有右子树（如果有右子树，那么 y 就不是前继了），至少有一个左子树或者没有子树，交换完之后就变成了第二种情况或者第一种情况了，接下来按照前面的方法删除 x（之前 y 在的位置）就可以了。