前言

二叉搜索树（Binary Search Tree，简称BST），也称为二叉查找树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

二叉搜索树中序遍历的结果是有序的。

由于这些特点，BST 可以应用于以下场景：

  • 快速查找

由于 BST 的特殊结构，可以通过比较节点值的大小来确定需要查找的节点所在位置。因此，BST 可以用于快速查找一组数据中是否存在某个元素，或者查找某个元素的前驱或后继等信息。

  • 排序

BST 可以实现对数据的快速排序。我们可以将所有数据依次插入到 BST 中，然后进行中序遍历，即可得到一个递增的有序序列。这种算法的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

  • 范围查找

在 BST 中，如果要寻找一个区间内的所有元素，只需要找到区间的两个端点对应的节点，然后进行中序遍历即可。

  • 删除和插入

对于一个已经建好的 BST，插入一个新节点或删除一个节点，只需要调整它的父节点和子节点之间的关系，不需要像数组那样进行大量的移动，因此效率非常高。

综上所述，二叉搜索树在实际应用中具有广泛的应用场景，是一种非常实用的数据结构。

算法实现

  • 二叉搜索树的储存结构

跟普通二叉树储存结构一样。

typedef struct {int data;struct BiTNode* left, * right;}BiTNode,*BiTree;

  • 建立二叉搜索树节点

用来建立新结点。

//建立二叉搜索树节点BiTree CreateNode(int data) {BiTree node = malloc(sizeof(BiTNode));node->data = data;node->left = NULL;node->right = NULL;return node;}

  • 插入元素

二叉搜索树的建立可以通过插入新元素实现。

基本流程：

如果当前元素在树中存在，则不需要插入（二叉搜索树性质）；

否则插入这个元素到 BST 中：
1.如果 BST 为空，则新元素成为根节点。
2.否则，按照二叉搜索树的特点进行查找：

  • 如果要插入的元素小于当前结点，则继续在当前结点的左子树中查找。如果左子树为空，则将新元素插入到左子树中。
  • 如果要插入的元素大于当前结点，则继续在当前结点的右子树中查找。如果右子树为空，则将新元素插入到右子树中。
//插入元素BiTree InsertNode(BiTree root, int data) {//若当前节点为空，建立新节点if (root == NULL) {root = CreateNode(data);return root;}/*若插入元素小于当前节点，则查找该节点左子树。若左子树为空，则将新元素插入到左子树中*/if (data data) {root->left = InsertNode(root->left, data);}//同上else if (data > root->data) {root->right = InsertNode(root->right, data);}return root;}

  • 查找元素

在BST中查找某个元素。

基本流程：

  1. 从根节点开始，比较要查找的元素和当前结点的元素大小关系。
  2. 如果相等，则返回当前结点。
  3. 如果要查找的元素小于当前结点，则继续在当前结点的左子树中查找。
  4. 如果要查找的元素大于当前结点，则继续在当前结点的右子树中查找。
  5. 如果找到了要查找的元素，则返回当前节点，否则返回 NULL。
//查找元素BiTree SearchNode(BiTree root, int data) {//若当前节点为空，返回NULLif (root == NULL) {return NULL;}//若查找值小于当前节点，则查找当前节点的左子树if (data data) {return SearchNode(root->left, data);}//若查找值大于当前节点，则查找当前节点的右子树else if (data > root->data) {return SearchNode(root->right, data);}//查找值等于当前节点，返回当前节点else {return root;}}

  • 查找最小元素

基本流程：

  1. 如果 BST 为空，则没有最小值，直接返回 NULL。

  2. 如果 BST 不为空，那么最小值一定是存在于 BST 的最左边的结点。

  3. 从根节点开始，一直向左走，直到到达最左边的结点（即最小结点）为止。

//查找最小节点BiTree FindMin(BiTree root) {if (root == NULL) {return NULL;}else if (root->left == NULL) {return root;}else {return FindMin(root->left);}}

  • 删除元素

删除操作开始看有点麻烦，不过跟着走一遍流程还是很简单的。

基本流程：

1.首先，在 BST 中查找要删除的元素。

2.如果要删除的元素不在 BST 中，则返回 NULL。
3.如果要删除的元素在 BST 中，分为以下三种情况：

  • 要删除的结点是叶子结点（即没有子节点），直接删除该结点即可。
  • 要删除的结点只有一个子节点，用子节点来替换当前结点即可。
  • 要删除的结点有两个子节点，用它的右子树中最小元素来替换当前结点元素，然后在右子树中删除最小元素。
//删除节点BiTree DeleteNode(BiTree root, int data) {//查找要删除的元素，未找到返回NULLif (root == NULL) {return root;}//要删除元素小于当前节点，则继续查找它的左子树else if (data data) {root->left = DeleteNode(root->left, data);}//要删除元素大于当前节点，则继续查找它的右子树else if (data > root->data) {root->right = DeleteNode(root->right, data);}//找到要删除元素时else {//若要删除节点没有子节点，则直接删除if (root->left == NULL && root->right == NULL) {free(root);root = NULL;}//若要删除节点没有左子树，则用右子树替换当前节点else if (root->left == NULL) {BiTree temp = root;root = root->right;free(temp);}//若要删除节点没有右子树，则用左子树替换当前节点else if (root->right == NULL) {BiTree temp = root;root = root->left;free(temp);}/*当要删除节点有左右子树时，查找它右子树中最小元素，将该最小元素替换当前节点，然后删除它右子树的最小元素*/else {BiTree temp = FindMin(root->right);root->data = temp->data;root->right = DeleteNode(root->right, temp->data);}}return root;}

  • 遍历

和普通二叉树遍历一样，写个简单的递归中序遍历。

//中序遍历void InOrderTraversal(BiTree root) {if (root != NULL) {InOrderTraversal(root->left);printf("%d ", root->data);InOrderTraversal(root->right);}}

运行代码,构造如下图所示二叉搜索树：

执行操作插入新元素2、删除节点5、查找最小元素、查找元素2，输出结果。

运行结果如下：

总结

以上是关于二叉搜索树的一些基础知识和操作流程。二叉搜索树是一种常用的数据结构，在实际开发中应用广泛。它可以快速地实现数据的查找、插入和删除等操作，并且具有遍历操作，可以对 BST 中的数据进行排序。在工程实践中，二叉搜索树可以用于实现字典、关键字索引和数据压缩等场景。

当然，BST 也有一些缺点，主要是在遇到极端情况时，比如树的深度很大，会出现退化，在某些操作上的时间复杂度会退化成 O(n)，不再具有快速的操作效率。为了解决这个问题，需要进行 AVL 树或红黑树等平衡二叉搜索树的优化。

总之，了解二叉搜索树是程序员必备的基础知识之一，希望本文的总结能够对你有所帮助。