C++ 二叉搜索树（BST）核心原理与实现

二分查找虽也能实现 O(log₂N) 的查找效率，但存在明显缺陷：

• 依赖支持随机访问的结构（如数组），且需提前排序；
• 插入 / 删除效率低：数组中插入 / 删除元素需挪动大量数据，时间复杂度为 O(N)。

而 BST 无需提前排序，且插入 / 删除时仅需修改节点指针，避免了数据挪动，这也是其在动态数据场景中更具优势的原因。

三. 二叉搜索树的实战实现：基于 BinarySearchTree.h

采用 C++ 模板实现，支持泛型 K，核心包含节点结构定义与BST 类的三大操作（插入、查找、删除），同时提供中序遍历接口验证有序性。

3.1 节点结构定义：BSTreeNode

BST 的节点需存储'值'与'左右子树指针'，模板化设计使其可适配 int、string 等多种类型：

#include <iostream>
using namespace std;

template <class K>
struct BSTreeNode {
    BSTreeNode<K>* _left;   // 左子树指针
    BSTreeNode<K>* _right;  // 右子树指针
    K _key;                 // 节点键值

    // 构造函数：初始化指针为空，键值为传入值
    BSTreeNode(const K& key) : _left(nullptr), _right(nullptr), _key(key) {}
};

3.2 BST 类核心操作：Insert、Find、Erase

BST 类封装了树的根节点 _root，并通过私有辅助函数 _InOrder 实现中序遍历。以下是三大核心操作的详细实现与解析：

3.2.1 插入操作（Insert）

插入的核心逻辑是'按 BST 规则找到空位置，创建新节点并链接'，步骤如下：

1. 若树为空（_root == nullptr），直接创建根节点；
2. 树非空时，用 cur 指针遍历树：
   • 若 cur->_key < 插入值：向右子树移动（cur = cur->_right）；
   • 若 cur->_key > 插入值：向左子树移动（cur = cur->_left）；
   • 若值相等（不支持插入），返回 false。

找到空位置后，通过 parent 指针（记录 cur 的父节点）将新节点链接到树中。

代码实现（BinarySearchTree.h）：

template <class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    bool Insert(const K& key) {
        // 情况 1：树为空，直接创建根节点
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        // 情况 2：树非空，遍历找插入位置
        Node* parent = nullptr; // 记录 cur 的父节点
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right; // 比当前节点大，向右走
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;  // 比当前节点小，向左走
            } else {
                // 键值已存在，不支持插入，返回 false
                return false;
            }
        }
        // 创建新节点，并链接到 parent 的左/右孩子
        cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur; // 插入值比 parent 大，作为右孩子
        } else {
            parent->_left = cur;  // 插入值比 parent 小，作为左孩子
        }
        return true;
    }

    // 中序遍历：验证 BST 的有序性
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

private:
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);      // 遍历左子树
        cout << root->_key << " "; // 访问当前节点
        _InOrder(root->_right);     // 遍历右子树
    }

    Node* _root = nullptr; // 树的根节点，初始为空
};

3.2.2 查找操作（Find）

查找的逻辑与插入类似，按 BST 规则遍历树，步骤如下：

1. 从根节点 _root 开始，用 cur 指针遍历；
2. 若 cur->_key < 目标值：向右走；若 cur->_key > 目标值：向左走；
3. 找到目标值返回 true，遍历到空节点（未找到）返回 false。

代码实现（BinarySearchTree.h）：

bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key) {
            cur = cur->_right; // 目标值大，向右找
        } else if (cur->_key > key) {
            cur = cur->_left;  // 目标值小，向左找
        } else {
            // 找到目标值，返回 true
            return true;
        }
    }
    // 遍历到空，未找到
    return false;
}

3.2.3 删除操作（Erase）：最复杂的核心操作

删除的难点在于'删除节点后，需保持 BST 的规则不变'。根据删除节点（记为 cur）的子节点数量，分为 4 种情况，其中前 3 种可合并处理，第 4 种需用'替换法'删除：

代码实现（BinarySearchTree.h）：

bool Erase(const K& key) {
    Node* parent = nullptr;
    Node* cur = _root;
    // 第一步：找到要删除的节点 cur
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 第二步：找到节点，按子节点情况处理删除
            // 情况 2：左子树为空，右子树非空
            if (cur->_left == nullptr) {
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (cur == parent->_left) parent->_left = cur->_right;
                    else parent->_right = cur->_right;
                }
                delete cur;
                return true;
            }
            // 情况 3：右子树为空，左子树非空
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (cur == parent->_left) parent->_left = cur->_left;
                    else parent->_right = cur->_left;
                }
                delete cur;
                return true;
            }
            // 情况 4：左右子树均非空（替换法删除）
            else {
                // 找 cur 右子树的最小节点（最左节点）作为替换节点
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 替换：将 replace 的键值赋给 cur
                cur->_key = replace->_key;
                // 删除 replace 节点（replace 的左子树为空，符合情况 2）
                if (replaceParent->_left == replace) replaceParent->_left = replace->_right;
                else replaceParent->_right = replace->_right;
                delete replace;
                return true;
            }
        }
    }
    // 未找到要删除的节点
    return false;
}

四. 实战测试：基于实战代码验证 BST 操作

test.cpp 通过引入 BinarySearchTree.h，实现 BST 的插入、删除与中序遍历验证，代码如下：

#include "BinarySearchTree.h"

int main() {
    // 测试数据：插入序列
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree<int> t;

    // 1. 插入所有元素
    for (auto& e : a) {
        t.Insert(e);
    }
    cout << "插入后中序遍历（应有序）：";
    t.InOrder(); // 输出：1 3 4 6 7 8 10 13 14

    // 2. 删除测试：逐步删除节点，验证有序性
    t.Erase(3); // 删除左子树非空、右子树非空的节点（情况 4）
    cout << "删除 3 后中序遍历：";
    t.InOrder(); // 输出：1 4 6 7 8 10 13 14

    t.Erase(8); // 删除根节点（左右子树非空，情况 4）
    cout << "删除 8 后中序遍历：";
    t.InOrder(); // 输出：1 4 6 7 10 13 14

    t.Erase(1); // 删除叶子节点（左右子树为空，情况 1）
    cout << "删除 1 后中序遍历：";
    t.InOrder(); // 输出：4 6 7 10 13 14

    t.Erase(10); // 删除右子树非空、左子树非空的节点（情况 4）
    cout << "删除 10 后中序遍历：";
    t.InOrder(); // 输出：4 6 7 13 14

    // 3. 清空树（删除所有元素）
    for (auto& e : a) {
        t.Erase(e);
    }
    cout << "清空后中序遍历（空行）：";
    t.InOrder(); // 输出空行

    return 0;
}

结果符合预期，证明 BST 的插入、删除操作均保持了**'中序遍历有序'**的核心特性。

五. BST 的扩展：key/value 模型（支持映射场景）

上述实现是'key 模型'（仅存储键值，用于判断'存在性'，不能修改），但实际场景中常需'key-value 模型'（键值对应数据，如字典、统计次数）。BinarySearchTree.h 可扩展为模板 template<class K, class V>，节点同时存储 _key 和 _value。

5.1 key-value 模型节点与类实现

// key-value 模型节点
template <class K, class V>
struct BSTreeNode {
    K _key;
    V _value;
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;

    BSTreeNode(const K& key, const V& value) : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

// key-value 模型 BST 类
template <class K, class V>
class BSTree {
    typedef BSTreeNode<K, V> Node;
public:
    // 插入：需传入 key 和 value
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 不支持重复 key
            }
        }
        cur = new Node(key, value);
        if (parent->_key < key) parent->_right = cur;
        else parent->_left = cur;
        return true;
    }

    // 查找：返回节点指针，可通过节点访问 value
    Node* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) cur = cur->_right;
            else if (cur->_key > key) cur = cur->_left;
            else return cur; // 返回节点，后续可操作 value
        }
        return nullptr;
    }

    // erase 跟上面没区别，这里就不展示了

    // 中序遍历：输出 key 和 value
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

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

    Node* _root = nullptr;
};

5.2 key-value 模型实战场景

场景 1：简单字典（中英互译）

int main() {
    key_value::BSTree<string, string> dict;
    dict.Insert("sort", "排序");
    dict.Insert("string", "字符串");
    dict.Insert("insert", "插入");
    dict.Insert("erase", "删除");
    dict.Insert("move", "移动");
    dict.Insert("tree", "树");
    dict.Insert("tree", "树*****"); // 插入失败，可以看看插入的逻辑，主要是 key 判断

    string str;
    while (cin >> str) {
        auto* node = dict.Find(str);
        if (node) {
            cout << "->" << node->_value << endl;
        } else {
            cout << "无此单词，请重新输入" << endl;
        }
    }
    return 0;
}

场景 2：单词统计（统计水果出现次数）

int main() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    key_value::BSTree<string, int> CountTree;
    for (auto& str : arr) {
        auto ret = CountTree.Find(str);
        // 第一次出现，插入<水果，1>
        if (ret == nullptr) {
            CountTree.Insert(str, 1);
        } else {
            // 已出现，次数 +1
            ret->_value++;
        }
    }
    // 中序遍历：按水果名称升序输出次数
    CountTree.InOrder();
    return 0;
}

结语

二叉搜索树（BST）以'左小右大'的规则，实现了动态数据的有序管理，中序遍历的有序性与指针操作的灵活性是其核心优势。插入、查找逻辑直观，删除操作的场景化处理（尤其是替换法）则是掌握关键，但其性能受插入顺序影响大，单支树退化问题也为后续平衡树（AVL、红黑树）的学习埋下伏笔。作为基础树形结构，BST 是理解复杂数据结构设计逻辑的重要基石。