C++ 二叉搜索树 (BST) 原理与核心实现详解

2、BST 类核心操作

BST 类封装了树的根节点 _root，并通过私有辅助函数实现中序遍历。以下是三大核心操作的详细实现与解析。

2.1 插入操作（Insert）

插入的核心逻辑是'按 BST 规则找到空位置，创建新节点并链接'。步骤如下：

1. 若树为空（_root == nullptr），则直接新增结点，赋值给 _root。
2. 树非空时，用 cur 指针遍历树找到符合要求的空位置：
   • 若 cur->_key < 插入值：向右子树移动。
   • 若 cur->_key > 插入值：向左子树移动。
   • 若值相等（不支持插入），返回 false。

找到空位置后，通过 father 指针（记录 cur 的父亲节点）将新节点链接到树中。注意这里需要比较 key 与 father 的 key 来决定挂在哪一侧，而不是判断 father 的指针是否指向 cur。

template<class K>
class BSTree {
public:
    typedef BSTNode<K> Node;

    // 二叉搜索树的插入
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }

        Node* cur = _root;
        Node* father = nullptr;
        while (cur) {
            if (cur->_key > key) {
                father = cur;
                cur = cur->_left;
            } else if (cur->_key < key) {
                father = cur;
                cur = cur->_right;
            } else {
                // 相同则不符合插入规则，返回 false
                return false;
            }
        }
        
        cur = new Node(key);
        // 根据 key 大小关系决定挂在父亲节点的左侧还是右侧
        if (key < father->_key) {
            father->_left = cur;
        } else {
            father->_right = cur;
        }
        return true;
    }

    // 中序遍历
    void Print() {
        _Print(_root);
        cout << endl;
    }

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

private:
    Node* _root = nullptr;
};

测试示例：

void Test1() {
    int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    BSTree<int> bst1;
    for (auto e : arr) {
        bst1.Insert(e);
    }
    bst1.Print(); // 输出应为有序序列
}

2.2 查找操作（Find）

查找的逻辑与插入类似，按 BST 规则遍历树：

1. 从根节点 _root 开始，用 cur 指针遍历。
2. 若 cur->_key < 目标值：向右走；若 cur->_key > 目标值：向左走。
3. 找到目标值返回 true，遍历到空节点（未找到）返回 false。

bool Find(const K& x) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key > x) {
            cur = cur->_left;
        } else if (cur->_key < x) {
            cur = cur->_right;
        } else {
            return true;
        }
    }
    return false;
}

2.3 删除操作（Erase）

删除是最复杂的核心操作。难点在于'删除节点后，需保持 BST 的规则不变'。根据删除节点（记为 cur）的子节点数量，分为几种情况：

1. 左右子树均为空（叶子节点）：直接删除 cur 节点，将 parent 指向 cur 的孩子指针置空。
2. 左子树为空，右子树非空：将 parent 指向 cur 的孩子指针，修改为指向 cur->_right。
3. 右子树为空，左子树非空：将 parent 指向 cur 的孩子指针，修改为指向 cur->_left。
4. 左右子树均非空：使用'替换法'。找 cur 右子树的'最小节点'（最左节点）或左子树的'最大节点'（最右节点），将替换节点的键值赋给 cur，然后删除替换节点（此时替换节点必属于情况 2 或 3）。

关键说明：选择'右子树最小节点'作为替换节点，是因为该节点的值是 cur 右子树中最小的，替换后仍满足 BST 规则（左子树 ≤ 根 ≤ 右子树）。

bool Erase(const K& x) {
    Node* cur = _root;
    Node* father = nullptr;
    
    // 先查找删除目标结点
    while (cur) {
        if (cur->_key > x) {
            father = cur;
            cur = cur->_left;
        } else if (cur->_key < x) {
            father = cur;
            cur = cur->_right;
        } else {
            // 情况 1 & 2: 左子树为空
            if (cur->_left == nullptr) {
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (father->_left == cur) {
                        father->_left = cur->_right;
                    } else {
                        father->_right = cur->_right;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 3: 右子树为空
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left; // 修正：应指向左孩子
                } else {
                    if (father->_left == cur) {
                        father->_left = cur->_left;
                    } else {
                        father->_right = cur->_left;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 4: 左右都不为空，替换法
            else {
                Node* min_right_father = nullptr;
                Node* min_right = cur->_right;
                // 找右子树最小结点
                while (min_right->_left) {
                    min_right_father = min_right;
                    min_right = min_right->_left;
                }
                
                cur->_key = min_right->_key;
                
                // 删除替换节点
                if (min_right_father == nullptr) {
                    cur->_right = min_right->_right;
                } else {
                    min_right_father->_left = min_right->_right;
                }
                delete min_right;
                return true;
            }
        }
    }
    return false;
}

四、BST 的扩展：Key/Value 模型

上述实现是'Key 模型'（仅存储键值，用于判断存在性），但在实际场景中，'Key/Value 模型'（键值对应数据，如字典、统计次数）更加有用。我们可以将模板扩展为 template<class K, class V>，节点同时存储 _key 和 _value。

1、Key/Value 模型节点与类实现

由于功能类似，主要区别在于部分函数需要考虑 value 的存放。另外，由于 BST 是动态开辟内存，必须手动实现析构函数防止内存泄漏；同时为了避免浅拷贝导致的重复释放问题，还需实现深拷贝的拷贝构造函数。

namespace key_value {
    template<class K, class V>
    class BSTNode {
    public:
        BSTNode(const K& key = 0, const V& value = 0)
            :_key(key), _value(value), _left(nullptr), _right(nullptr) {}
        K _key;
        V _value;
        BSTNode<K, V>* _left;
        BSTNode<K, V>* _right;
    };

    template<class K, class V>
    class BSTree {
    public:
        typedef BSTNode<K, V> Node;

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

        BSTree(const BSTree<K, V>& bst) {
            _root = Copy(bst._root);
        }

        BSTree() = default;

        bool Insert(const K& key, const V& value) {
            if (_root == nullptr) {
                _root = new Node(key, value);
                return true;
            }
            Node* cur = _root;
            Node* father = nullptr;
            while (cur) {
                if (cur->_key > key) {
                    father = cur;
                    cur = cur->_left;
                } else if (cur->_key < key) {
                    father = cur;
                    cur = cur->_right;
                } else {
                    return false;
                }
            }
            cur = new Node(key, value);
            if (key < father->_key) {
                father->_left = cur;
            } else {
                father->_right = cur;
            }
            return true;
        }

        void Print() {
            _Print(_root);
            cout << endl;
        }

        Node* Find(const K& x) {
            Node* cur = _root;
            while (cur) {
                if (cur->_key > x) {
                    cur = cur->_left;
                } else if (cur->_key < x) {
                    cur = cur->_right;
                } else {
                    return cur;
                }
            }
            return nullptr;
        }

        bool Erase(const K& x) {
            Node* cur = _root;
            Node* father = nullptr;
            while (cur) {
                if (cur->_key > x) {
                    father = cur;
                    cur = cur->_left;
                } else if (cur->_key < x) {
                    father = cur;
                    cur = cur->_right;
                } else {
                    if (cur->_left == nullptr) {
                        if (cur == _root) {
                            _root = cur->_right;
                        } else {
                            if (father->_left == cur) {
                                father->_left = cur->_right;
                            } else {
                                father->_right = cur->_right;
                            }
                        }
                        delete cur;
                        return true;
                    } else if (cur->_right == nullptr) {
                        if (cur == _root) {
                            _root = cur->_left;
                        } else {
                            if (father->_left == cur) {
                                father->_left = cur->_left;
                            } else {
                                father->_right = cur->_left;
                            }
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* min_right_father = nullptr;
                        Node* min_right = cur->_right;
                        while (min_right->_left) {
                            min_right_father = min_right;
                            min_right = min_right->_left;
                        }
                        cur->_key = min_right->_key;
                        cur->_value = min_right->_value;
                        if (min_right_father == nullptr) {
                            cur->_right = min_right->_right;
                        } else {
                            min_right_father->_left = min_right->_right;
                        }
                        delete min_right;
                        return true;
                    }
                }
            }
            return false;
        }

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

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

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

    private:
        Node* _root = nullptr;
    };
}

2、Key/Value 模型实战场景

场景 1：简单字典（中英互译） 树结构中存储 key（英文）和 value（中文），搜索时输入英文，即可找到对应的中文。

void Test2() {
    key_value::BSTree<string, string> dict;
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("insert", "输入");
    
    string str;
    while (cin >> str) {
        auto ret = dict.Find(str);
        if (ret) {
            cout << "->" << ret->_value << endl;
        } else {
            cout << "无此单词，请重新输入" << endl;
        }
    }
}

场景 2：单词统计 读取一个单词，查找是否存在。不存在则插入 <单词，1>；存在则查找到的结点对应的次数 ++。

void Test3() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "香蕉" };
    key_value::BSTree<string, int> countTree;
    
    for (const auto& str : arr) {
        auto ret = countTree.Find(str);
        if (ret == nullptr) {
            countTree.Insert(str, 1);
        } else {
            ret->_value++; // 找到结点后直接访问_value 再++
        }
    }
    countTree.Print();
}

结束语

到此，二叉搜索树的基础概念和功能实现就讲解完了。虽然中序遍历的有序性与指针操作的灵活性是其核心优势，但其性能受插入顺序影响大，容易导致单支树退化。我们在这里把 BST 的实现讲解得这么详细，也是为了后续学习平衡树（AVL、红黑树）埋下伏笔。作为基础树形结构，BST 是理解复杂数据结构设计逻辑的重要基石。