C++ 二叉搜索树详解：原理、实现与应用

相比传统深拷贝写法，Swap 惯用法避免了手动销毁旧节点和重新分配内存的繁琐过程，降低了出错概率。

4. 中序遍历封装

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

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

设计 InOrder() 接口是为了隐藏内部实现细节。用户只需调用公共接口即可遍历，无需关心 _root 指针或递归逻辑。这种封装遵循面向对象原则，降低了误操作风险，并增强了代码的可维护性。

三、核心操作：查找、插入与删除

1. 查找

从根节点开始比较：

• 若当前节点值小于目标值，向右子树查找。
• 若当前节点值大于目标值，向左子树查找。
• 若相等，则找到。

最大元素位于最右分枝端点，最小元素位于最左分枝端点。

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

2. 插入

二叉搜索树不能插入重复元素。新节点最终会成为叶子节点。

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

3. 删除

删除操作较为复杂，需处理四种情况：

1. 无孩子节点：直接删除。
2. 只有左孩子：父节点指向左孩子。
3. 只有右孩子：父节点指向右孩子。
4. 有左右孩子：替换法。用右子树中的最小值（或左子树最大值）替换待删除节点，再删除该最小值节点。

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 {
            // 找到了待删除节点
            // 情况 1: 左子节点为空
            if (cur->_left == nullptr) {
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (cur == parent->_right)
                        parent->_right = cur->_right;
                    else
                        parent->_left = cur->_right;
                }
                delete cur;
                return true;
            }
            // 情况 2: 右子节点为空
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (cur == parent->_right)
                        parent->_right = cur->_left;
                    else
                        parent->_left = cur->_left;
                }
                delete cur;
                return true;
            }
            // 情况 3: 左右子节点均不为空
            else {
                Node* rightMinParent = cur;
                Node* rightMin = cur->_right;
                // 找到右子树中最小节点
                while (rightMin->_left) {
                    rightMinParent = rightMin;
                    rightMin = rightMin->_left;
                }
                // 替换值
                cur->_key = rightMin->_key;
                // 删除最小节点
                if (rightMin == rightMinParent->_left)
                    rightMinParent->_left = rightMin->_right;
                else
                    rightMinParent->_right = rightMin->_right;
                delete rightMin;
                return true;
            }
        }
    }
    return false;
}

四、性能分析

插入和删除操作都必须先查找，因此查找效率决定了整体性能。

• 最优情况：完全二叉树，平均比较次数为 $O(\log_2 N)$。
• 最差情况：退化为单支树（类似链表），平均比较次数为 $O(N)$。

对于同一个关键码集合，插入次序不同会导致不同的树结构，进而影响性能。

五、应用——KV 模型

1. K 模型

仅存储 Key，用于判断是否存在。例如拼写检查器，词库单词作为 Key。

2. KV 模型

Key 对应 Value，即键值对。例如英汉词典（英文->中文）、词频统计（单词->次数）。

string strs[] = {"苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果"};
BSTree<string, int> countTree;
for (auto str : strs) {
    auto ret = countTree.Find(str);
    if (!ret) {
        countTree.Insert(str, 1);
    } else {
        ret->_value++;
    }
}
countTree.InOrder();

六、完整代码实现

#include <iostream>
using namespace std;

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

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

    template<class K, class V>
    class BSTree {
        typedef BSTreeNode<K, V> Node;
    public:
        BSTree() : _root(nullptr) {}

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

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

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

        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->_right)
                                parent->_right = cur->_right;
                            else
                                parent->_left = cur->_right;
                        }
                        delete cur;
                        return true;
                    } else if (cur->_right == nullptr) {
                        if (cur == _root) {
                            _root = cur->_left;
                        } else {
                            if (cur == parent->_right)
                                parent->_right = cur->_left;
                            else
                                parent->_left = cur->_left;
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* rightMinParent = cur;
                        Node* rightMin = cur->_right;
                        while (rightMin->_left) {
                            rightMinParent = rightMin;
                            rightMin = rightMin->_left;
                        }
                        cur->_key = rightMin->_key;
                        cur->_value = rightMin->_value;
                        if (rightMin == rightMinParent->_left)
                            rightMinParent->_left = rightMin->_right;
                        else
                            rightMinParent->_right = rightMin->_right;
                        delete rightMin;
                        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 << " " << root->_value << " ";
            _InOrder(root->_right);
        }

        Node* _root;
    };
}

七、关键实现细节

1. 模板参数的作用域

代码中出现两处 template <class K>，这是因为它们的作用域独立。

• 第一处定义 BSTreeNode 结构体的模板参数。
• 第二处定义 BSTree 类的模板参数。 尽管名字相同，但它们属于不同的模板上下文。在 BSTree 中使用 BSTreeNode<K> 时，需要显式传递参数以确保类型一致。

2. bool 与 status 的区别

• bool：内置布尔类型，仅表示 true 或 false。适用于简单的真假判断，如操作是否成功。
• status：通常指代枚举或扩展类型，可表示多种状态（如 SUCCESS, FAILURE, PENDING）。适用于需要更丰富上下文信息的场景。

在实际工程中，简单逻辑可用 bool，复杂状态流转建议使用 enum class Status。

3. 常见陷阱

• 递归终止条件：确保 root == nullptr 时正确返回。
• 指针自增/自减：在遍历过程中不要随意修改指针导致丢失父节点信息。
• 内存泄漏：删除节点后务必置空指针，析构函数中要清理整棵树。