[数据结构·树] 二叉查找树（BST）

你好！这是一个非常核心的数据结构问题。

首先，我来澄清一下：二叉查找树（Binary Search Tree, BST） 和 二叉排序树（Binary Sort Tree） 是 完全相同的概念，只是名字不同。它们都描述的是同一种数据结构。

---

🌳 什么是二叉查找树 (BST)？

二叉查找树（BST）是一种特殊的二叉树，它“有序”地组织数据，其定义如下：

1. 它首先是一棵二叉树（每个节点最多有两个子节点）。

2. 对于树中的任意一个节点，其左子树中所有节点的值都小于该节点的值。

3. 对于树中的任意一个节点，其右子树中所有节点的值都大于该节点的值。

4. 它的左、右子树也分别是二叉查找树。

注意： 这个定义通常不允许重复值。如果允许重复值，一种常见的约定是将其放在右子树（即右子树的值 >= 节点的值）。

---

🧠 主要实现什么功能？

二叉查找树的核心功能是提供高效的动态集合操作。它的主要优势在于：

1. 高效查找 (Search):

   • 这是它最主要的功能。要查找一个值，你从根节点开始比较：

     • 如果值相等，就找到了。

     • 如果值小于当前节点，就去左子树找。

     • 如果值大于当前节点，就去右子树找。

   • 在理想情况下（树比较“平衡”），每次比较都能排除掉大约一半的节点，因此查找的时间复杂度是 $O(\log n)$。

   • 最坏情况： 如果树退化成一个链表（例如，依次插入1, 2, 3, 4, 5），查找时间会退化到 $O(n)$。

2. 高效插入 (Insert) 和删除 (Delete):

   • 它允许你快速地插入新元素或删除已有元素，同时保持树的有序特性。

   • 这些操作的平均时间复杂度也是 $O(\log n)$，最坏情况也是 $O(n)$。

3. 排序 (Sorting):

   • 这也是它被称为“二叉排序树”的原因。如果你对一棵二叉查找树进行中序遍历（In-order Traversal，即“左 -> 根 -> 右”的顺序），你会得到一个严格递增的有序序列。

---

💻 C 语言代码实现

下面是一个二叉查找树在 C 语言中的基本实现，包括：

• 节点定义 (struct Node)

• 创建新节点 (createNode)

• 插入节点 (insert)

• 查找节点 (search)

• 删除节点 (deleteNode) - 这是最复杂的部分

• 中序遍历 (inOrder)

#include <stdio.h>
#include <stdlib.h>

// 1. 定义二叉查找树的节点结构
struct Node {
    int data;                 // 节点存储的数据
    struct Node* left;      // 指向左子节点的指针
    struct Node* right;     // 指向右子节点的指针
};

// 2. 创建一个新节点
struct Node* createNode(int data) {
    // 为新节点分配内存
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("内存分配失败!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 3. 插入一个新节点 (递归实现)
// 返回值是插入新节点后(可能)的
struct Node* insert(struct Node* node, int data) {
    // 基础情况：如果树(或子树)为空，则在此处创建新节点
    if (node == NULL) {
        return createNode(data);
    }

    // 递归步骤：
    if (data < node->data) {
        // 如果数据较小，插入到左子树
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        // 如果数据较大，插入到右子树
        node->right = insert(node->right, data);
    }
    // (如果 data == node->data，则什么也不做，不插入重复值)

    return node; // 返回(可能已更新的)节点指针
}

// 4. 查找一个节点 (递归实现)
struct Node* search(struct Node* root, int data) {
    // 基础情况 1: 没找到 (到达NULL)
    if (root == NULL) {
        return NULL;
    }
    // 基础情况 2: 找到了
    if (root->data == data) {
        return root;
    }

    // 递归步骤：
    if (data < root->data) {
        return search(root->left, data); // 往左找
    } else {
        return search(root->right, data); // 往右找
    }
}

// 5. 中序遍历 (LDR: 左-根-右)
// 这将按排序顺序打印所有节点
void inOrder(struct Node* root) {
    if (root != NULL) {
        inOrder(root->left);          // 1. 遍历左子树
        printf("%d ", root->data);    // 2. 访问根节点
        inOrder(root->right);         // 3. 遍历右子树
    }
}

// (辅助函数) 查找子树中的最小节点 (用于删除)
struct Node* findMin(struct Node* node) {
    struct Node* current = node;
    // 最小的节点总是在最左边
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

// 6. 删除一个节点 (递归实现)
struct Node* deleteNode(struct Node* root, int data) {
    if (root == NULL) {
        return root; // 没找到
    }

    // 1. 查找要删除的节点
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } 
    // 2. 找到了要删除的节点 (data == root->data)
    else {
        // 情况 1: 节点没有子节点 或 只有一个子节点
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp; // 返回右子节点 (或NULL)
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp; // 返回左子节点
        }

        // 情况 2: 节点有两个子节点
        // 找到右子树中的最小节点 (即中序遍历的后继者)
        struct Node* temp = findMin(root->right);

        // 将后继者的值复制到当前节点
        root->data = temp->data;

        // 从右子树中删除那个后继者节点
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// (辅助函数) 释放整棵树的内存
void freeTree(struct Node* node) {
    if (node == NULL) return;
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

// 主函数：演示如何使用
int main() {
    struct Node* root = NULL; // 初始化一棵空树

    // 插入节点
    // 注意：第一次插入时，必须将返回值赋给root
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // 中序遍历 (应该输出: 20 30 40 50 60 70 80)
    printf("中序遍历 (排序结果): ");
    inOrder(root);
    printf("\n");

    // 查找节点
    int keyToSearch = 40;
    if (search(root, keyToSearch) != NULL) {
        printf("找到了 %d\n", keyToSearch);
    } else {
        printf("未找到 %d\n", keyToSearch);
    }

    keyToSearch = 90;
    if (search(root, keyToSearch) != NULL) {
        printf("找到了 %d\n", keyToSearch);
    } else {
        printf("未找到 %d\n", keyToSearch);
    }
    
    // 删除节点
    printf("\n删除节点 20 (叶子节点)\n");
    root = deleteNode(root, 20);
    printf("中序遍历: ");
    inOrder(root);
    printf("\n");

    printf("\n删除节点 30 (只有一个子节点)\n");
    root = deleteNode(root, 30);
    printf("中序遍历: ");
    inOrder(root);
    printf("\n");

    printf("\n删除节点 50 (有两个子节点)\n");
    root = deleteNode(root, 50);
    printf("中序遍历: ");
    inOrder(root);
    printf("\n");

    // 释放内存
    freeTree(root);

    return 0;
}

---

总结

• 二叉查找树 (BST) 和 二叉排序树 是同义词。

• 核心特性： 左 < 根 < 右。

• 主要功能： 高效的查找、插入、删除（平均 $O(\log n)$）和排序（通过中序遍历）。

• 最大缺点： 在最坏情况下会退化成链表（$O(n)$），这导致了更高级的平衡二叉查找树（如 AVL 树和红黑树）的出现。

你是否想了解更多关于二叉查找树的平衡问题（比如AVL树或红黑树）？