二叉排序树（BST，Binary Search Tree）实现

二叉排序树（BST）是一种二叉树，它满足以下性质：

每个节点的值都大于其左子树的所有节点值。
每个节点的值都小于其右子树的所有节点值。
左子树和右子树本身也是二叉排序树。

BST 允许高效的插入、删除和查找操作，其平均时间复杂度为 O(log n)，但在最坏情况下（如退化成链表），时间复杂度可能为 O(n)。

实现思路

我们要实现一个 二叉排序树（BST），并支持以下操作：

插入 (insert)：在 BST 中插入一个新值，保持 BST 性质。
查找 (search)：查找 BST 是否包含某个值。
删除 (remove)：删除 BST 中的某个值，并保持 BST 结构。
中序遍历 (inorder_traversal)：按照升序顺序打印 BST 中的元素。

1. 数据结构

BST 由 节点（Node） 组成，每个节点包含：

值 (value)
左子树 (left)
右子树 (right)

#include <iostream>

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

2. 插入操作

插入操作遵循 BST 规则：

若插入值小于当前节点值，则递归插入到左子树；
若插入值大于当前节点值，则递归插入到右子树；
若当前节点为空，则创建新节点。

class BST {
private:
    TreeNode* root;

    // 递归插入节点
    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->value) {
            node->left = insert(node->left, val);
        } else if (val > node->value) {
            node->right = insert(node->right, val);
        }
        return node;
    }

public:
    BST() : root(nullptr) {}

    void insert(int val) {
        root = insert(root, val);
    }
};

3. 查找操作

查找操作遵循 BST 规则：

若当前节点为空，返回 false；
若当前节点值等于目标值，返回 true；
若目标值小于当前节点值，则递归查找左子树；
若目标值大于当前节点值，则递归查找右子树。

class BST {
    // 递归查找
    bool search(TreeNode* node, int val) {
        if (!node) return false;
        if (val == node->value) return true;
        return val < node->value ? search(node->left, val) : search(node->right, val);
    }

public:
    bool search(int val) {
        return search(root, val);
    }
};

4. 删除操作

删除节点有三种情况：

删除的节点是叶子节点（无子节点）：
- 直接删除该节点，返回 nullptr 作为父节点的新子节点。
删除的节点有一个子节点：
- 让其唯一的子节点接替它的位置。
删除的节点有两个子节点：
- 找到 右子树中的最小节点（后继节点），用该节点的值替换要删除的节点的值，然后递归删除后继节点。

TreeNode* remove(TreeNode* node, int val) {
    if (!node) return nullptr;

    if (val < node->value) {
        node->left = remove(node->left, val);
    } else if (val > node->value) {
        node->right = remove(node->right, val);
    } else {
        // 情况 1 & 2: 叶子节点或仅有一个子节点
        if (!node->left) {
            TreeNode* rightChild = node->right;
            delete node;
            return rightChild;
        } else if (!node->right) {
            TreeNode* leftChild = node->left;
            delete node;
            return leftChild;
        }

        // 情况 3: 找到右子树的最小值（后继节点）
        TreeNode* successor = node->right;
        while (successor->left) {
            successor = successor->left;
        }

        node->value = successor->value;  // 用后继节点值替换当前节点
        node->right = remove(node->right, successor->value);  // 删除后继节点
    }

    return node;
}

public:
void remove(int val) {
    root = remove(root, val);
}

5. 中序遍历

中序遍历（左-根-右）会按照升序顺序输出 BST 的值。

void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    std::cout << node->value << " ";
    inorder(node->right);
}

public:
void inorder_traversal() {
    inorder(root);
    std::cout << std::endl;
}

完整代码

#include <iostream>

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;

    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->value) node->left = insert(node->left, val);
        else if (val > node->value) node->right = insert(node->right, val);
        return node;
    }

    bool search(TreeNode* node, int val) {
        if (!node) return false;
        if (val == node->value) return true;
        return val < node->value ? search(node->left, val) : search(node->right, val);
    }

    TreeNode* remove(TreeNode* node, int val) {
        if (!node) return nullptr;
        if (val < node->value) node->left = remove(node->left, val);
        else if (val > node->value) node->right = remove(node->right, val);
        else {
            if (!node->left) {
                TreeNode* rightChild = node->right;
                delete node;
                return rightChild;
            } else if (!node->right) {
                TreeNode* leftChild = node->left;
                delete node;
                return leftChild;
            }
            TreeNode* successor = node->right;
            while (successor->left) successor = successor->left;
            node->value = successor->value;
            node->right = remove(node->right, successor->value);
        }
        return node;
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        std::cout << node->value << " ";
        inorder(node->right);
    }

public:
    BST() : root(nullptr) {}

    void insert(int val) { root = insert(root, val); }
    bool search(int val) { return search(root, val); }
    void remove(int val) { root = remove(root, val); }
    void inorder_traversal() { inorder(root); std::cout << std::endl; }
};

int main() {
    BST tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(4);
    tree.insert(6);

    tree.inorder_traversal(); // 3 4 5 6 7
    tree.remove(5);
    tree.inorder_traversal(); // 3 4 6 7

    return 0;
}