C++ 模拟实现二叉搜索树

3.3 插入逻辑

插入时遵循 BST 规则：从根节点开始比较，小于向左，大于向右，直到找到空位置。

• 若树为空，直接创建新节点作为根；
• 若树不为空，遍历找到合适位置后插入；
• 若不支持重复值，遇到相等键值则返回失败。

template<class K>
bool BSTree<K>::Insert(const K& key) {
    // 情况 1：树为空，直接创建根节点
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    // 情况 2：树不为空，遍历找到插入位置
    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;
}

3.4 查找逻辑

查找过程相对简单，沿路径向下比较即可。若遍历至空节点仍未找到，说明不存在。

template<class K>
bool BSTree<K>::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; // 遍历至空，查找失败
}

3.5 删除逻辑

删除是 BST 中最复杂的操作，需分三种情况处理：

1. 叶子节点或仅有一个孩子：直接将父节点指针指向其非空孩子（或 null）；
2. 有两个孩子：采用'替换法'，用右子树的最小节点（或左子树的最大节点）替换当前节点，再删除该替换节点。

注意处理根节点被删除的特殊情况，以及释放内存防止泄漏。

template<class K>
bool BSTree<K>::Erase(const K& key) {
    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 {
            // 找到要删除的节点
            // 情况 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;
            }
            // 情况 2：右孩子为空（叶子节点/仅左孩子）
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (parent->_right == cur) {
                        parent->_right = cur->_left;
                    } else {
                        parent->_left = cur->_left;
                    }
                }
                delete cur;
            }
            // 情况 3：左右孩子都不为空（替换法删除）
            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; // 未找到目标节点
}

3.6 中序遍历验证

BST 的中序遍历结果应为升序序列，这是验证树结构正确性的最直接方式。

template<class K>
void BSTree<K>::_InOrder(Node* root) {
    if (root == nullptr) return;
    _InOrder(root->_left);   // 遍历左子树
    cout << root->_key << " "; // 访问当前节点
    _InOrder(root->_right);  // 遍历右子树
}

template<class K>
void BSTree<K>::InOrder() {
    _InOrder(_root);
    cout << endl;
}

四、两种典型应用场景

4.1 仅关键码（Key）场景

节点只存 Key，适用于判断元素是否存在。例如车牌验证、单词拼写检查等。

4.2 键值对（Key/Value）场景

节点存 Key 和 Value，适用于字典映射、词频统计等。此时查找通常返回 Value 的引用或指针以便修改。

以下是键值对版本的简要实现思路：

// 键值对版本的节点结构
template<class K, class T>
struct BSTNodeKV {
    K _key;
    T _value;
    BSTNodeKV<K, T>* _left;
    BSTNodeKV<K, T>* _right;

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

// 键值对版本的二叉搜索树
template<class K, class T>
class BSTreeKV {
    using Node = BSTNodeKV<K, T>;
public:
    bool Insert(const K& key, const T& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            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; // 不支持重复 key
            }
        }
        cur = new Node(key, value);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }

    T* 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->_value); // 返回 value 地址，支持修改
            }
        }
        return nullptr;
    }

    // 删除逻辑与 Key 版本一致，略
    bool Erase(const K& key) { /* ... */ return false; }

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

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

五、代码易错说明

1. 指针管理：删除节点时必须确保父节点指针更新正确，特别是根节点被删除的情况。
2. 内存泄漏：每次 new 都要对应 delete，尤其是替换法删除时，别忘了释放替换节点。
3. 边界条件：空树操作、单节点树操作容易出错，测试时需覆盖这些场景。
4. 命名规范：区分 parent 和 replaceParent，避免在复杂逻辑中混淆指针含义。

六、测试示例

通过中序遍历输出升序序列，可以直观验证插入和删除的正确性。

void TestBSTree() {
    BSTree<int> t;
    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    for (auto e : a) {
        t.Insert(e);
    }
    cout << "中序遍历（升序）：";
    t.InOrder(); // 输出：1 3 4 6 7 8 10 13 14

    cout << "查找 6：" << (t.Find(6) ? "成功" : "失败") << endl;
    cout << "删除 3：" << (t.Erase(3) ? "成功" : "失败") << endl;
    cout << "删除后中序遍历：";
    t.InOrder(); // 输出：1 4 6 7 8 10 13 14
}

void TestBSTreeKV() {
    BSTreeKV<string, int> dict;
    dict.Insert("apple", 1);
    dict.Insert("banana", 2);
    dict.Insert("orange", 3);
    cout << "中序遍历键值对：";
    dict.InOrder();

    // 修改 banana 的 value
    int* p = dict.Find("banana");
    if (p) {
        *p = 20;
    }
    cout << "修改后中序遍历：";
    dict.InOrder();
}

int main() {
    TestBSTree();
    TestBSTreeKV();
    return 0;
}

七、总结

二叉搜索树的核心在于维持'有序性'。本文实现的版本涵盖了基础功能，但在实际工程应用中（如 STL 容器），通常会结合平衡算法（如红黑树）来保证性能稳定。理解 BST 的底层逻辑，是掌握高级数据结构与算法的关键一步。