C++ 二叉搜索树：从原理到增删查实现

C++ 二叉搜索树：从原理到增删查实现

二叉搜索树（Binary Search Tree, BST）是数据结构中非常基础且重要的一种树形结构。它通过简单的规则实现了高效的查找、插入和删除操作，是理解平衡树（如 AVL、红黑树）的基石。

1. 核心概念与性质

一棵二叉搜索树满足以下两个条件：

1. 若左子树不空，则左子树上所有节点的值均小于根节点的值。
2. 若右子树不空，则右子树上所有节点的值均大于根节点的值。
3. 左右子树也分别为二叉搜索树。

简单来说，就是对于任意节点，其左子树的所有值都小于它，右子树的所有值都大于它。这一特性决定了我们不需要遍历整棵树就能快速定位目标。

2. 基本操作逻辑

我们将树封装为一个类 BSTree，内部维护一个指向根节点的指针 _root。

2.1 查找节点

查找的逻辑与二分查找类似。从根节点出发，比较当前节点值与目标值：

• 如果目标值小于当前值，向左走；
• 如果目标值大于当前值，向右走；
• 如果相等，则找到目标。

在平衡状态下，时间复杂度为 O(log n)。最坏情况下（退化为链表），复杂度为 O(n)。

// 查找节点
Node* find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key)
            cur = cur->_left;
        else if (val > cur->_key)
            cur = cur->_right;
        else
            break; // 找到目标
    }
    return cur;
}

2.2 插入节点

插入时需要保持 BST 的性质。流程如下：

1. 查找位置：从根节点开始，根据大小关系向下遍历，直到遇到空指针。
2. 创建节点：在空指针处新建节点。

注意两点：

• BST 通常不允许重复键值，若已存在则直接返回。
• 需要记录父节点 curPre，以便在遍历结束时将新节点挂接到正确的位置。

bool insert(const K& val) {
    // 空树情况
    if (_root == nullptr) {
        _root = new Node(val);
        return true;
    }

    Node* cur = _root;
    Node* curPre = nullptr;
    
    while (cur) {
        if (val == cur->_key)
            return false; // 重复值，不插入
        else if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else {
            curPre = cur;
            cur = cur->_right;
        }
    }

    // 此时 cur 为空，curPre 是父节点
    Node* newNode = new Node(val);
    if (curPre->_left == nullptr)
        curPre->_left = newNode;
    else
        curPre->_right = newNode;

    return true;
}

2.3 删除节点

删除是最复杂的操作，需分三种情况处理，确保删除后仍满足 BST 性质：

1. 叶子节点：直接删除。
2. 只有一个孩子：用孩子替换该节点。
3. 有两个孩子：不能直接删除，需用替代节点覆盖原节点值。通常选择右子树的最小节点（或左子树的最大节点）来替换。

以右子树最小节点为例：找到该节点，将其值赋给待删除节点，然后删除该最小节点（此时最小节点最多只有一个右孩子，简化了删除逻辑）。

bool erase(const K& val) {
    if (_root == nullptr)
        return false;

    Node* cur = _root;
    Node* curPre = nullptr;

    // 1. 查找待删除节点
    while (cur) {
        if (val < cur->_key) {
            curPre = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            curPre = cur;
            cur = cur->_right;
        } else
            break;
    }

    if (cur == nullptr)
        return false;

    // 2. 处理删除逻辑
    // 情况 0 或 1 个孩子
    if (cur->_left == nullptr || cur->_right == nullptr) {
        Node* curNext = cur->_left ? cur->_left : cur->_right;
        
        if (cur != _root) {
            if (curPre->_left == cur)
                curPre->_left = curNext;
            else
                curPre->_right = curNext;
        } else {
            _root = curNext;
        }
        delete cur;
    } 
    // 情况 2 个孩子
    else {
        // 找右子树最小节点
        Node* rightMin = cur->_right;
        Node* rightMinPre = cur;
        while (rightMin->_left) {
            rightMinPre = rightMin;
            rightMin = rightMin->_left;
        }

        // 用最小节点的值覆盖
        cur->_key = rightMin->_key;

        // 删除最小节点（它最多只有右孩子）
        Node* rightMinNext = rightMin->_right;
        if (rightMinPre->_left == rightMin)
            rightMinPre->_left = rightMinNext;
        else
            rightMinPre->_right = rightMinNext;
        delete rightMin;
    }
    return true;
}

3. 完整代码实现

下面是完整的类定义及测试示例，包含了析构函数和遍历功能。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

template<class K>
struct BSTNode {
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;

    BSTNode(const K& val) : _left(nullptr), _right(nullptr), _key(val) {}
};

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;

    BSTree() : _root(nullptr) {}

    ~BSTree() {
        destroy(_root);
        _root = nullptr;
    }

    Node* find(const K& val) {
        Node* cur = _root;
        while (cur) {
            if (val < cur->_key)
                cur = cur->_left;
            else if (val > cur->_key)
                cur = cur->_right;
            else
                break;
        }
        return cur;
    }

    bool insert(const K& val) {
        if (_root == nullptr) {
            _root = new Node(val);
            return true;
        }
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val == cur->_key)
                return false;
            else if (val < cur->_key) {
                curPre = cur;
                cur = cur->_left;
            } else {
                curPre = cur;
                cur = cur->_right;
            }
        }
        Node* newNode = new Node(val);
        if (curPre->_left == nullptr)
            curPre->_left = newNode;
        else
            curPre->_right = newNode;
        return true;
    }

    bool erase(const K& val) {
        if (_root == nullptr)
            return false;
        Node* cur = _root;
        Node* curPre = nullptr;
        while (cur) {
            if (val < cur->_key) {
                curPre = cur;
                cur = cur->_left;
            } else if (val > cur->_key) {
                curPre = cur;
                cur = cur->_right;
            } else
                break;
        }
        if (cur == nullptr)
            return false;

        if (cur->_left == nullptr || cur->_right == nullptr) {
            Node* curNext = cur->_left ? cur->_left : cur->_right;
            if (cur != _root) {
                if (curPre->_left == cur)
                    curPre->_left = curNext;
                else
                    curPre->_right = curNext;
            } else {
                _root = curNext;
            }
            delete cur;
        } else {
            Node* rightMin = cur->_right;
            Node* rightMinPre = cur;
            while (rightMin->_left) {
                rightMinPre = rightMin;
                rightMin = rightMin->_left;
            }
            cur->_key = rightMin->_key;
            Node* rightMinNext = rightMin->_right;
            if (rightMinPre->_left == rightMin)
                rightMinPre->_left = rightMinNext;
            else
                rightMinPre->_right = rightMinNext;
            delete rightMin;
        }
        return true;
    }

    void inOrder() {
        _inOrder(_root);
        cout << endl;
    }

private:
    Node* _root;

    void destroy(Node* root) {
        if (root == nullptr)
            return;
        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

    void _inOrder(Node* root) {
        if (root == nullptr)
            return;
        _inOrder(root->_left);
        cout << root->_key << " ";
        _inOrder(root->_right);
    }
};

void testBST() {
    BSTree<int> bst;
    vector<int> arr = {8, 3, 10, 1, 6, 14, 5, 7, 13};
    
    cout << "=== 1. 创建二叉搜索树 ===\n";
    cout << "初始数据：-> ";
    for (const auto& e : arr) cout << e << " ";
    cout << "\n";
    
    cout << "创建完成数据：-> ";
    for (const auto& e : arr) bst.insert(e);
    bst.inOrder();

    cout << "=== 2. 查找数据 ===\n";
    cout << "查找不存在数据：28 查找结果：" << (bst.find(28) ? "Found" : "Not Found") << endl;
    cout << "查找存在数据：14 查找结果：" << (bst.find(14) ? "Found" : "Not Found") << endl;

    cout << "\n=== 3. 删除数据 ===\n";
    cout << "删除前的序列：->";
    bst.inOrder();
    cout << "删除节点 6 后的序列：->";
    bst.erase(6);
    bst.inOrder();
    cout << "删除不存在的节点 86 后的序列：->";
    bst.erase(86);
    bst.inOrder();
}

4. 应用场景

4.1 K 模型

只存储 Key，用于判断元素是否存在。例如拼写检查器，将词库单词作为 Key 构建 BST，检索单词是否存在即可。

4.2 KV 模型

存储 Key-Value 对。例如英汉词典，Key 为英文单词，Value 为中文释义；或者统计单词出现次数，Key 为单词，Value 为计数。

// KV 模型示例：统计单词频率
template<class K, class V>
struct BSTNodeKV {
    K _key;
    V _value;
    BSTNodeKV<K, V>* _left;
    BSTNodeKV<K, V>* _right;
    BSTNodeKV(const K& k, const V& v) : _key(k), _value(v), _left(nullptr), _right(nullptr) {}
};

// 使用逻辑类似，只需在节点中增加 value 字段，并在插入时更新 value

5. 总结

二叉搜索树的核心价值在于利用'左小右大'的规则，换取了平均 O(log n) 的操作效率。无论是 K 模型还是 KV 模型，都能通过其核心操作快速适配。

但需注意，BST 的性能高度依赖树的平衡性。如果插入的数据是有序的，树会退化成链表，性能降至 O(n)。这也是后续学习 AVL 树、红黑树等平衡二叉搜索树的原因——它们通过自平衡机制维持树的高度，兼顾了简洁性与稳定性。