C++ 模拟实现二叉搜索树

3.2 树的类封装

将二叉搜索树封装为类，根节点作为私有成员（保证数据封装性），使用 C++11 的 using 简化节点类型名：

template <class K>
class BSTree {
    using Node = BSTNode<K>; // C++11 类型别名，替代传统 typedef
public:
    // 核心操作声明（插入、查找、删除、中序遍历）
    bool Insert(const K& key);
    bool Find(const K& key);
    bool Erase(const K& key);
    void InOrder();

private:
    // 私有辅助函数：中序遍历的递归实现
    void _InOrder(Node* root);
    Node* _root = nullptr; // 根节点指针，初始化为空
};

3.3 插入

插入逻辑：

• 若树为空，直接创建新节点作为根节点；
• 若树不为空，按二叉搜索树规则遍历：插入值大于当前节点则向右走，小于则向左走，找到空位置后插入新节点；

若不支持重复值插入，遇到与当前节点值相等的情况则返回插入失败。

template <class K>
bool BSTree<K>::Insert(const K& key) {
    // 情况 1：树为空，直接创建根节点
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    // 情况 2：树不为空，遍历找到插入位置
    Node* cur = _root;
    Node* parent = nullptr; // 记录当前节点的父节点（用于后续连接新节点）

    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right; // 大于当前节点，向右遍历
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left; // 小于当前节点，向左遍历
        } else {
            // 找到相等值，不插入（若支持重复值，可改为向右/左遍历）
            return false;
        }
    }

    // 找到空位置，创建新节点并连接到父节点
    cur = new Node(key);
    if (parent->_key < key) {
        parent->_right = cur; // 新节点值更大，连接到父节点右孩子
    } else {
        parent->_left = cur; // 新节点值更小，连接到父节点左孩子
    }
    return true;
}

3.4 查找

• 从根节点开始比较：查找值大于根节点则向右查找，小于则向左查找；
• 遍历至空节点则说明查找失败，找到相等值则返回成功；

若支持重复值，通常要求返回中序遍历的第一个目标值（需额外逻辑，本文实现基础版）。

template <class K>
bool BSTree<K>::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 true; // 找到目标值，返回成功
        }
    }
    return false; // 遍历至空，查找失败
}

3.5 删除

删除逻辑：

1. 先查找目标节点：不存在则返回失败；
2. 存在则分三种情况处理（合并叶子节点与单孩子节点逻辑）：
   • 左孩子为空：将父节点的对应指针指向当前节点的右孩子，删除当前节点；
   • 右孩子为空：将父节点的对应指针指向当前节点的左孩子，删除当前节点；

左右孩子都不为空：采用'替换法'——找右子树的最小节点（最左节点）或左子树的最大节点（最右节点）替换目标节点，再删除替换节点（替换节点必为单孩子/叶子节点）。

template <class K>
bool BSTree<K>::Erase(const K& key) {
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到要删除的节点

            // 情况 1：左孩子为空（叶子节点/仅右孩子）
            if (cur->_left == nullptr) {
                // 处理根节点删除的特殊情况
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    // 父节点的左/右指针指向当前节点的右孩子
                    if (parent->_left == cur) {
                        parent->_left = cur->_right;
                    } else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur; // 释放节点内存
            }
            // 情况 2：右孩子为空（叶子节点/仅左孩子）
            else if (cur->_right == nullptr) {
                // 处理根节点删除的特殊情况
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    // 父节点的左/右指针指向当前节点的左孩子
                    if (parent->_right == cur) {
                        parent->_right = cur->_left;
                    } else {
                        parent->_left = cur->_left;
                    }
                }
                delete cur; // 释放节点内存
            }
            // 情况 3：左右孩子都不为空（替换法删除）
            else {
                // 找右子树的最小节点（最左节点）作为替换节点
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                while (replace->_left) // 遍历至右子树最左节点
                {
                    replaceParent = replace;
                    replace = replace->_left;
                }

                // 替换目标节点的关键码
                cur->_key = replace->_key;

                // 连接替换节点的父节点与替换节点的右孩子（替换节点左必为空）
                if (replaceParent->_left == replace) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace; // 释放替换节点内存
            }
            return true; // 删除成功
        }
    }
    return false; // 未找到目标节点，删除失败
}

3.6 中序遍历（验证二叉搜索树的有序性）

二叉搜索树的中序遍历结果为升序序列，是验证树结构正确性的核心方式。通过'公有接口 + 私有递归函数'的方式访问私有根节点：

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

template <class K>
void BSTree<K>::InOrder() {
    _InOrder(_root); // 调用私有递归函数
    cout << endl;
}

四、二叉搜索树的两种应用场景

4.1 仅关键码（key）场景

核心特点

节点仅存储关键码 key，操作仅关注'key 是否存在'，不支持修改 key（修改会破坏树的结构），支持增删查。

典型场景

• 小区车库车牌验证：录入业主车牌，车辆进场时查找车牌是否存在；
• 英文单词拼写检查：将词库单词存入树，遍历文章单词并查找，不存在则标红。

4.2 键值对（key/value）场景

核心特点

节点存储 key + value（value 为任意类型），增删查以 key 为关键字，支持修改 value（不修改 key）。

典型场景

• 中英互译字典：key 为英文单词，value 为中文释义，查找 key 即可获取释义；
• 停车计费系统：key 为车牌，value 为入场时间，离场时查找 key 计算停车时长；
• 单词词频统计：key 为单词，value 为出现次数，查找单词存在则 value++。

// 键值对版本的节点结构
template <class K, class T>
struct BSTNodeKV {
    K _key;
    T _value;
    BSTNodeKV<K, T>* _left;
    BSTNodeKV<K, T>* _right;

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

// 键值对版本的二叉搜索树
template <class K, class T>
class BSTreeKV {
    using Node = BSTNodeKV<K, T>;
public:
    // 插入键值对
    bool Insert(const K& key, const T& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        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;
    }

    // 查找 key 并返回 value 的指针（方便修改 value）
    T* 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); // 返回 value 地址，支持修改
            }
        }
        return nullptr; // 查找失败
    }

    // 删除（逻辑与 key 版本一致，略）
    bool Erase(const K& key) {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    } else {
                        if (parent->_left == cur) parent->_left = cur->_right;
                        else parent->_right = cur->_right;
                    }
                    delete cur;
                } else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    } else {
                        if (parent->_right == cur) parent->_right = cur->_left;
                        else parent->_left = cur->_left;
                    }
                    delete cur;
                } else {
                    Node* replaceParent = cur;
                    Node* replace = cur->_right;
                    while (replace->_left) {
                        replaceParent = replace;
                        replace = replace->_left;
                    }
                    // 替换 key 和 value
                    cur->_key = replace->_key;
                    cur->_value = replace->_value;
                    if (replaceParent->_left == replace) replaceParent->_left = replace->_right;
                    else replaceParent->_right = replace->_right;
                    delete replace;
                }
                return true;
            }
        }
        return false;
    }

    // 中序遍历（打印 key 和 value）
    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

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

五、测试示例

// 测试 key 版本的二叉搜索树
void TestBSTree() {
    BSTree<int> t;
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    for (auto e : a) {
        t.Insert(e);
    }
    cout << "中序遍历（升序）：";
    t.InOrder(); // 输出：1 3 4 6 7 8 10 13 14
    cout << "查找 6：" << (t.Find(6) ? "成功" : "失败") << endl; // 成功
    cout << "删除 3：" << (t.Erase(3) ? "成功" : "失败") << endl; // 成功
    cout << "删除后中序遍历：";
    t.InOrder(); // 输出：1 4 6 7 8 10 13 14
}

// 测试键值对版本的二叉搜索树
void TestBSTreeKV() {
    BSTreeKV<string, int> dict;
    dict.Insert("apple", 1);
    dict.Insert("banana", 2);
    dict.Insert("orange", 3);
    cout << "中序遍历键值对：";
    dict.InOrder(); // 输出：key: apple, value: 1 key: banana, value: 2 key: orange, value: 3

    // 修改 banana 的 value
    int* p = dict.Find("banana");
    if (p) {
        *p = 20;
    }
    cout << "修改后中序遍历：";
    dict.InOrder(); // 输出：key: apple, value: 1 key: banana, value: 20 key: orange, value: 3
}

int main() {
    TestBSTree();
    TestBSTreeKV();
    return 0;
}

总结

二叉搜索树的核心是'有序性'，其所有操作均围绕这一特性展开。本文实现的基础版本覆盖了二叉搜索树的核心功能，而实际工程中（如 C++ 标准库）会通过红黑树对其进行平衡优化，避免单支树的性能退化。理解二叉搜索树的底层逻辑，是掌握关联式容器、高效检索算法的关键基础。