C++ 二叉搜索树（BST）详解与实现

为什么用 = default？

当类中包含其他构造函数（如拷贝构造、赋值重载）时，编译器不再自动生成默认构造函数。如果此时仍需要默认构造行为，必须显式声明 BSTree() = default;。这不仅告诉编译器'我需要默认行为'，还能保持代码语义清晰，表明没有额外的初始化逻辑。

析构函数

~BSTree() { Destory(_root); }

void Destory(Node* root) {
    if (root == nullptr) return;
    Destory(root->_left);
    Destory(root->_right);
    delete root;
}

3. 赋值运算符重载

这里推荐一种高效写法，利用 swap 和临时对象自动管理资源。

BSTree<K>& operator=(const BSTree<K>& t) {
    swap(_root, t._root);
    return *this;
}

执行流程解析：

1. 传参：调用 operator= 时，参数 t 是通过值传递进来的副本。这意味着会先调用拷贝构造函数复制一份 tree2 的数据给 t。
2. Swap：交换 this->_root 和 t._root。此时 tree1 拿到了 tree2 的根指针，而 t 拿到了 tree1 原来的根指针。
3. 返回：返回 *this 支持链式赋值。
4. 清理：函数结束时，临时变量 t 被销毁，其析构函数会自动释放之前属于 tree1 的那部分内存。

这种方式避免了手动 Destroy 旧数据再深拷贝新数据的繁琐过程，既安全又高效。

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 设为私有辅助函数，对外只暴露 InOrder()，这是典型的封装设计。用户无需关心递归细节和根节点指针，降低了误操作风险，也便于未来修改实现逻辑而不影响外部接口。

三、查找与插入

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 为空，parent 指向待插入位置的前驱
    if (parent->_key < key) parent->_right = new Node(key);
    else parent->_left = new Node(key);
    return true;
}

注意：判断插入方向时，依据的是 key 与 parent->_key 的大小关系，而不是 parent 的子节点是否为空。这是初学者容易混淆的地方。

四、删除操作

删除是最复杂的部分，分为三种情况：

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 {
            // 找到了待删除节点
            // 情况 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)$。

因此，对于同一个关键码集合，插入次序不同会导致树的结构差异巨大。在实际工程中，通常会配合平衡树（如 AVL、红黑树）来保证性能稳定。

六、应用——KV 模型

1. K 模型：仅存储 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++;
    }
}

七、完整代码与重难点

模板类设计要点

代码中出现两处 template <class K>，这是因为作用域独立。BSTreeNode 的 K 和 BSTree 的 K 虽然同名但互不干扰。在 BSTree 内部实例化 Node 时，需显式传递 K。

返回值类型选择

• bool：适用于简单的真假判断（如查找成功与否）。
• status：通常指代枚举类型，适用于表示多种状态（成功、失败、处理中等），信息量更丰富。

在 BST 操作中，由于主要关注'是否存在'或'是否插入成功'，使用 bool 最为直观；若需区分具体错误原因，可考虑扩展为状态枚举。

以下是整合后的完整实现框架（含 KV 支持）：

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 << " ";
            _InOrder(root->_right);
        }

        Node* _root;
    };
}

掌握这些细节后，你就能构建一个健壮的二叉搜索树了。实际开发中记得关注平衡性问题，必要时引入旋转操作。