C++ 二叉搜索树基础实现：插入、查找、删除与遍历

前言

本文从零开始实现一棵 C++ 二叉搜索树（BST）：先定义节点结构，再实现核心的插入、查找与中序遍历，最后详细讲解删除操作（涵盖叶子节点、单子节点与双子节点三种情况）。通过完整代码与逻辑梳理，帮助读者深入理解二叉搜索树的底层原理。

1. 什么是二叉搜索树？

二叉搜索树（Binary Search Tree, BST）又称二叉排序树。它或者是一棵空树，或者是具有以下性质的二叉树：

• 左子树上所有节点的值均小于等于根节点的值；
• 右子树上所有节点的值均大于等于根节点的值；
• 它的左右子树也分别为二叉搜索树。

注意：二叉搜索树是否支持插入相等的值取决于具体使用场景。例如，标准库中的 std::set/std::map 不允许重复键，而 std::multiset/std::multimap 则允许。

2. 二叉搜索树性能分析

• 最优情况：树为完全二叉树（或接近完全二叉树），高度为 $O(\log_2 N)$。
• 最差情况：树退化为单支树（类似链表），高度为 $O(N)$。
• 平均时间复杂度：查找、插入、删除的平均时间复杂度为 $O(\log N)$，最差为 $O(N)$。

说明：虽然二分查找也能达到 $O(\log N)$ 的查找效率，但存在两大局限：

1. 数据必须存储在支持下标随机访问的连续结构中，且保持有序。
2. 插入和删除操作效率低下，通常需要移动大量元素。

3. Key 类型二叉搜索树的实现

本节实现仅存储键值（Key）的二叉搜索树，对应标准库中 set 容器的底层逻辑（默认元素唯一）。

节点结构

template<class K>
struct BSTNode {
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;

    BSTNode(const K& key = K())
        : _key(key), _left(nullptr), _right(nullptr) {}
};

类结构

template<class K>
class BSTree {
    using Node = BSTNode<K>;
public:
    // 接口声明...
private:
    Node* _root = nullptr;
};

3.1 插入

思路：

1. 若树为空，直接创建新节点作为根节点。
2. 若树非空，从根节点开始遍历。若插入值小于当前节点，则向左走；若大于当前节点，则向右走。
3. 记录父节点指针，找到空位后根据大小关系将新节点链接为父节点的左孩子或右孩子。
4. 若遇到相等值，默认返回 false（不支持重复插入）。

bool Insert(const K& key) {
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false; // 键已存在
        }
    }

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

3.2 中序遍历

二叉搜索树的中序遍历结果为一个有序序列（升序）。由于根节点 _root 为私有成员，需封装一个公共接口调用私有递归函数。

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

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

3.3 查找

思路：从根节点开始比较，目标值小则向左，大则向右。若遍历至空仍未找到，则返回 false。

bool Find(const K& val) {
    Node* cur = _root;
    while (cur) {
        if (val < cur->_key) {
            cur = cur->_left;
        } else if (val > cur->_key) {
            cur = cur->_right;
        } else {
            return true; // 找到目标值
        }
    }
    return false;
}

3.4 删除

思路：删除节点需分情况处理：

1. 左子树为空：直接用右子树替代当前节点。
2. 右子树为空：直接用左子树替代当前节点。
3. 左右子树均不为空：采用替换法。找到右子树的最小节点（或左子树的最大节点），将其值赋给待删除节点，然后删除该替代节点（此时替代节点必为情况1或2）。

bool Erase(const K& val) {
    Node* parent = nullptr;
    Node* cur = _root;

    // 1. 查找待删除节点
    while (cur) {
        if (val < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (val > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            break; // 找到目标节点
        }
    }
    if (cur == nullptr) return false; // 未找到

    // 2. 执行删除
    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;
    } 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;
    } 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;
}

4. Key-Value 类型二叉搜索树的实现

本节实现键值对（Key-Value）存储的二叉搜索树，对应标准库中 map 容器的底层逻辑。除节点多存储一个 _value 外，核心逻辑与 Key 类型一致。此处补充完整的构造、拷贝、赋值与析构实现。

节点结构

template<class K, class V>
struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;

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

类结构

template<class K, class V>
class BSTree {
    using Node = BSTNode<K, V>;
public:
    // 接口声明...
private:
    Node* _root = nullptr;
};

4.1 构造函数

// 默认构造
BSTree() = default;

// 拷贝构造（深拷贝）
BSTree(const BSTree& tree) {
    _root = Copy(tree._root);
}

Node* Copy(Node* root) {
    if (root == nullptr) return nullptr;
    Node* newNode = new Node(root->_key, root->_value);
    newNode->_left = Copy(root->_left);
    newNode->_right = Copy(root->_right);
    return newNode;
}

4.2 赋值重载

采用现代 C++ 的拷贝并交换（Copy-and-Swap）惯用法，保证强异常安全。

BSTree& operator=(BSTree tree) {
    std::swap(_root, tree._root);
    return *this;
}

4.3 析构函数

使用后序遍历释放节点，防止提前释放父节点导致子节点内存泄漏。

~BSTree() {
    Destroy(_root);
    _root = nullptr;
}

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

4.4 插入

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 (key < cur->_key) {
            parent = cur;
            cur = cur->_left;
        } else if (key > cur->_key) {
            parent = cur;
            cur = cur->_right;
        } else {
            return false;
        }
    }

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

总结

本文实现了二叉搜索树的基础版本，涵盖了插入、查找、删除及遍历等核心操作，并区分了 Key 类型与 Key-Value 类型的实现差异。该版本未处理树退化问题（如 AVL 树或红黑树的平衡操作），但已完整呈现 BST 的核心逻辑，为后续学习平衡二叉搜索树及标准库关联容器打下坚实基础。