C++ 二叉搜索树原理与实现

核心操作实现

插入操作

插入逻辑遵循 BST 性质：比当前节点小往左走，大往右走，直到找到空位。如果树为空，直接设为根节点。

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        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;
        }
    }

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

查找操作

从根节点开始比较，路径唯一，最多遍历树的高度次。

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 {
            return true;
        }
    }
    return false;
}

删除操作

删除是 BST 中最复杂的操作，需分情况讨论：

1. 无孩子或仅一个孩子：直接将父节点的指针指向孩子的另一侧（或直接指向 null）。
2. 有两个孩子：不能直接删除，否则无法安置两个子树。通常用右子树的最小值（中序后继）或左子树的最大值替换当前节点的值，然后递归删除那个被替换的节点（此时该节点必为情况 1 或 2）。

这里采用交换键值的方法简化指针操作：

bool Erase(const K& key) {
    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 {
            // 找到了待删除节点
            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;
            } 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;
            } else {
                // 两个孩子，找右子树最小值替代
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                // 交换键值
                std::swap(cur->_key, minRight->_key);
                // 删除 minRight 节点（此时它必然没有左孩子）
                if (pMinRight->_left == minRight) {
                    pMinRight->_left = minRight->_right;
                } else {
                    pMinRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

中序遍历

利用递归特性，先左后根再右，即可得到有序序列。

void InOrder() {
    _InOrder(_root);
    std::cout << std::endl;
}

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

Key-Value 结构变体

在实际应用中，往往需要存储键值对（Key-Value）。除了存储 key 外，还需增加 value 字段。增删查逻辑不变，依然以 key 为准，但允许修改 value。

namespace key_value {
template<class K, class V>
struct BSTreeNode {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;

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

// 类定义逻辑同上，仅需调整构造函数及打印输出
// ... (省略部分重复代码，逻辑一致)
};

典型应用场景

Key 模式

• 车牌识别系统：录入业主车牌号，车辆进入时扫描比对，存在则放行。
• 拼写检查：将词库存入 BST，读取文章单词进行快速查找匹配。

Key-Value 模式

• 翻译字典：Key 为英文，Value 为中文，输入即查。
• 停车场计费：记录车牌与入场时间，出场时计算时长并扣费。
• 词频统计：Key 为单词，Value 为出现次数，遇到新单词初始化计数，已存在则累加。

以上便是二叉搜索树的核心原理与 C++ 实现细节。理解这些基础结构，对于后续学习更复杂的平衡树（如红黑树）至关重要。