C++ 二叉搜索树详解：原理、操作与 Key/Value 场景

3.3 完整的类定义

提供插入、查找、删除等基本操作的接口设计。由于树的递归起始条件通常是根节点，而根节点往往被封装在私有成员中，因此内部递归函数通常需要传入根节点指针。

4. 插入操作详解

4.1 算法流程

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

1. 树为空，直接新增结点，赋值给 root 指针；
2. 树不空，比当前结点大往右走，小往左走，找到空位置插入；
3. 若不允许相等值，遇到相等直接返回 false；若允许，需统一方向（如一律往右）。

4.2 代码实践

以下实现为不允许插入相等值的版本：

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    bool 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;
    }
private:
    Node* _root = nullptr;
};

4.3 验证：中序遍历

利用 BST 的中序遍历必然有序的特性验证插入正确性。编写时采用'套一层'的方式，外部调用不传参，内部递归函数接收根节点。

5. 查找操作实现

5.1 查找算法

1. 从根开始比较，目标值比根大则向右，比根小则向左；
2. 最多查找高度次，走到空仍未找到则不存在；
3. 若支持重复值，通常要求查找中序的第一个匹配项。

5.2 代码实践

查找操作可以使用递归或迭代实现，迭代方式在避免栈溢出方面更具优势。

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

6. 删除操作深度解析

删除是 BST 中最复杂的部分，面试中常考。首先需要定位待删除节点及其父节点。

6.1 四种情况

假设要删除的节点为 N：

1. N 左右孩子均为空：直接删除 N，将父节点对应指针置空。
2. N 左孩子为空，右孩子不为空：父节点指针指向 N 的右孩子。
3. N 右孩子为空，左孩子不为空：父节点指针指向 N 的左孩子。
4. N 左右孩子均不为空：无法直接删除。需用替换法。

6.2 替换策略

对于情况 4，找 N 左子树的最大节点（最右节点）或右子树的最小节点（最左节点）替代 N。这两个节点中任意一个放到 N 的位置，都满足 BST 规则。替代本质是交换值，然后转为删除替代节点（此时替代节点符合情况 2 或 3）。

6.3 代码实现要点

• 需判断被删除节点是否为根节点。
• 需判断替代节点的父节点是否就是当前节点（当右子树最小节点即为右孩子时）。
• 释放内存前务必更新指针连接。

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 {
            // 找到节点 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;
                cur->_value = replace->_value; // 若有 value
                if (replaceParent->_left == replace) replaceParent->_left = replace->_right;
                else replaceParent->_right = replace->_right;
                delete replace;
                return true;
            }
        }
    }
    return false;
}

7. 完整代码示例与实践演示

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

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

    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 (parent->_left == cur) parent->_left = cur->_right;
                    else parent->_right = cur->_right;
                    delete cur; return true;
                }
                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;
                }
                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;
    }

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

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

private:
    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.InOrder();
    t.Erase(8); t.InOrder();
    t.Erase(1); t.InOrder();
    return 0;
}

8. 使用场景

8.1 Key 搜索场景

只存储 Key，用于判断元素是否存在。

• 场景 1：小区车库车牌识别系统，录入车牌号，进出扫描比对。
• 场景 2：英文文章拼写检查，词库存入 BST，读取单词查找。

8.2 Key / Value 使用场景

Key 对应 Value，支持修改 Value，但不支持修改 Key。

• 场景 1：中英互译字典，Key 为英文，Value 为中文。
• 场景 2：停车场计费，Key 为车牌，Value 为入场时间。
• 场景 3：词频统计，Key 为单词，Value 为出现次数。

8.3 代码实现差异

Key/Value 模式下，Node 结构体增加 V _value 成员，Insert/Erase 时需同步处理 Value 的拷贝或覆盖。

本文涵盖了二叉搜索树的核心原理、C++ 实现细节及典型应用场景。掌握 BST 是理解高级数据结构（如红黑树、STL map/set）的关键基石。