C++ 二叉搜索树：原理、核心操作与 Key/Value 应用

类封装

为了隐藏私有成员 _root，通常采用内部递归辅助函数的模式。这样外部调用时无需传递根节点指针。

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 不允许相等的值插入
    bool Insert(const K& key);
    bool Find(const K& key);
    bool Erase(const K& key);
    void InOrder();
private:
    Node* _root = nullptr;
    void _InOrder(Node* root);
};

核心操作详解

插入操作

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

1. 树为空，直接赋值给 root；
2. 树不空，比当前结点大往右走，小往左走，找到空位插入；
3. 若遇到相等值，本实现返回 false。

template<class K>
bool BSTree<K>::Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        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; // 已存在
        }
    }

    cur = new Node(key);
    if (parent->_key < key) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    return true;
}

查找操作

利用排序特性，通过比较键值快速定位。最多查找高度次，走到空仍未找到则不存在。

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;
}

删除操作

删除是 BST 中最复杂的操作，需先定位节点，再分情况处理：

1. 左子树为空：用右孩子替代；
2. 右子树为空：用左孩子替代；
3. 左右子树均不为空：用右子树的最小节点（中序后继）或左子树的最大节点替代当前节点的值，然后删除该替代节点。

注意：当替代节点的父节点就是当前节点时，逻辑需特殊判断，避免断链。

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

    // 1. 查找要删除的节点
    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到目标节点 cur
            // 情况 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;
                return true;
            }
            // 情况 2：右子树为空
            else if (cur->_right == nullptr) {
                if (cur == _root) _root = cur->_left;
                else if (parent->_left == cur) parent->_left = cur->_left;
                else parent->_right = cur->_left;
                delete cur;
                return true;
            }
            // 情况 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;
}

中序遍历验证

中序遍历结果应为有序序列，常用于验证 BST 的正确性。

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;
}

应用场景

Key 搜索场景

仅存储 Key，用于判断元素是否存在。例如车牌识别系统、单词拼写检查。

Key / Value 使用场景

每个 Key 对应一个 Value，支持修改 Value 但不能修改 Key（否则破坏树结构）。例如字典翻译、停车计费统计。

namespace key_value {
    template<class K, class V>
    struct BSTreeNode {
        BSTreeNode<K,V>* _left;
        BSTreeNode<K,V>* _right;
        K _key;
        V _value;
        // ... 构造函数略
    };
    // ... 类实现逻辑同上，增加 value 字段处理
}

完整代码示例

SearchBinaryTree.h

#pragma once
#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) {}
};

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
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;
};

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SearchBinaryTree.h"

int main() {
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree<int> t;
    for (auto e : a) t.Insert(e);
    
    t.InOrder(); // 输出：1 3 4 6 7 8 10 13 14
    
    t.Erase(3);
    t.Erase(8);
    t.InOrder(); // 再次验证顺序
    return 0;
}

运行结果应始终保持中序遍历有序，证明删除逻辑正确。