C++ 实现二叉搜索树：迭代与递归详解

二叉搜索树的概念与作用

二叉搜索树（Binary Search Tree, BST），又称二叉排序树，具备以下关键特性：

• 若左子树非空，则左子树上所有节点的值均小于根节点的值。
• 若右子树非空，则右子树上所有节点的值均大于根节点的值。
• 左右子树本身也必须分别为二叉搜索树。

其核心价值在于：搜索，利用大小关系快速定位目标；以及排序，对二叉搜索树进行中序遍历即可得到有序序列。它是学习 AVL 树、红黑树等高级平衡树结构的基石，也是 C++ STL 中 std::map 与 std::set 的内部原理基础。

核心操作实现

在 C++ 中实现 BST，通常定义一个包含键值 _k 和指向左右子节点的指针结构体。实现分为迭代法和递归法，前者侧重于循环控制与指针移动，后者依赖于函数栈帧与引用传递。

第 1 步：查找节点

目的：验证特定键值是否存在于树中。
逻辑入口：从根节点 _root 开始比较。

迭代实现时，定义当前节点指针 cur。当 cur->_k < k 时向右子树走，> 时向左子树走，相等则返回真。若到达空节点仍未找到，则返回假。

bool Find(const K& k)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_k < k)
            cur = cur->_right;
        else if (cur->_k > k)
            cur = cur->_left;
        else
            return true;
    }
    return false;
}

递归实现更简洁，通过 _FindR(root, k) 调用。若 root 为空返回 nullptr；根据大小关系决定递归方向；命中则返回当前节点指针。

Node* FindR(Node* root, const K& k)
{
    if (root == nullptr) return nullptr;
    if (root->_k > k)   return FindR(root->_left, k);
    if (root->_k < k)   return FindR(root->_right, k);
    return root;
}

第 2 步：插入新节点

目的：保持 BST 有序性插入元素。若已存在则拒绝插入。
前置准备：需追踪父节点 parent。

迭代版先判空，空树直接建立根。否则用 cur 和 parent 向下遍历，定位插入位置后建立新节点连接至 parent 的左侧或右侧。

bool InsertNode(const K& k)
{
    if (_root == nullptr)
    {
        _root = new Node(k); return true;
    }
    Node* cur = _root; Node* parent = nullptr;
    while (cur)
    {
        if (cur->_k < k) { parent = cur; cur = cur->_right; }
        else if (cur->_k > k) { parent = cur; cur = cur->_left; }
        else return false; // 已存在
    }
    cur = new Node(k);
    if (parent->_k < k) parent->_right = cur;
    else parent->_left = cur;
    return true;
}

递归版使用引用 Node*& root，这使得修改实参 _root 变得简单。若传入为空则新建节点赋值；若不匹配则进入对应子树；命中则返回失败。

bool _InsertR(Node*& root, const K& k)
{
    if (root == nullptr) { root = new Node(k); return true; }
    if (root->_k < k) return _InsertR(root->_right, k);
    if (root->_k > k) return _InsertR(root->_left, k);
    return false;
}

第 3 步：删除节点

风险提醒：删除节点涉及复杂的指针重构，处理不当易导致内存泄漏或断链。务必确保在断开指针前备份需要保存的子树信息。

策略分类：

1. 无左子树：将其右子树（可能为空）接管当前节点位置。
2. 无右子树：将其左子树接管当前节点位置。
3. 左右都有：寻找中序后继（右子树中的最小节点 min），交换键值，然后递归/迭代删除该后继节点。

迭代实现逻辑严密但冗长，需分别处理根节点、左孩子替换和右孩子替换三种情况。递归版则在找到目标后，对于双分支情况，使用中序后继交换键值，随后递归删除右子树中的最小节点，最后释放原节点内存。

bool _EraseR(Node*& root, const K& k)
{
    if (root == nullptr) return false;
    if (root->_k < k) return _EraseR(root->_right, k);
    if (root->_k > k) return _EraseR(root->_left, k);
    
    // 找到节点
    Node* del = root;
    if (root->_left == nullptr)       root = root->_right;
    else if (root->_right == nullptr) root = root->_left;
    else
    {
        // 找右子树最小节点
        Node* min = root->_right;
        while(min->_left) min = min->_left;
        swap(min->_k, root->_k);
        return _EraseR(root->_right, k);
    }
    delete del; return true;
}

Key-Value 模型的常见应用

实际开发中，二叉搜索树常演化为 Tree<K, V> 形式，即每个节点携带 _v 值。这在 C++ STL 底层结构中极为普遍。

场景一：简易字典映射

将英文单词作为 Key，中文释义作为 Value 存入 BST。通过查找 Key 可快速获取对应的 Value。

BSTree wordDict;
wordDict.InsertNode("man", "男人");
wordDict.InsertNode("Earth", "地球");

string query = "Earth";
auto ret = wordDict.Find(query);
if (ret) cout << ret->_v << endl; // 输出: 地球

场景二：词频统计（计数）

利用 BST 存储字符串与出现次数（int）。遇到未记录单词初始化计数为 1，已存在则递增计数。

string arr[] = { "a","b","e","e","b","a","n" };
BSTree counter;
for (auto& str : arr)
{
    auto ret = counter.Find(str);
    if (ret) (ret->_v)++;           // 找到则计数+1
    else counter.InsertNode(str, 1); // 找不到则插入
}

总结

掌握二叉搜索树的实现是进阶高级算法的关键一步。它虽然可能在极端情况下退化为链表，但其基本的插入、删除与查找逻辑构成了现代编程语言的容器库核心。以上就是 C++ 二叉搜索树实现与应用的详细内容，更多关于 C++ 数据结构与 STL 底层实现的资料请关注本站其它相关文章！