二叉搜索树（BST）：查找、插入、删除与退化的深渊

#include <iostream>
 
struct Node
{
    int _key;
    Node* _left = nullptr;
    Node* _right = nullptr;
    explicit Node(int k) : _key(k) {}
};
 
// 递归求树的高度：空树高度为 0，否则等于"左右子树高度的较大者 + 1"
int Height(Node* root)
{
    if (root == nullptr)
    {
        return 0;                       // 递归边界：空子树高度记 0
    }
    int leftH = Height(root->_left);    // 问题缩小：先算左子树高度
    int rightH = Height(root->_right);  // 再算右子树高度
    return (leftH > rightH ? leftH : rightH) + 1;  // 取较大者，再算上自己这一层
}
 
int main()
{
    Node* root = new Node(1);
    root->_left = new Node(2);
    root->_right = new Node(3);
    root->_left->_left = new Node(4);
    root->_left->_right = new Node(5);
 
    std::cout << "树的高度 = " << Height(root) << std::endl;  // 输出 3
    delete root->_left->_left;
    delete root->_left->_right;
    delete root->_left;
    delete root->_right;
    delete root;
    return 0;
}

#include <iostream>
 
struct Node
{
    int _key;
    Node* _left = nullptr;
    Node* _right = nullptr;
    explicit Node(int k) : _key(k) {}
};
 
// 判断是否是严格的二叉搜索树（不允许相等的重复值）
// min / max 分别表示"当前允许的下界、上界"；为 nullptr 表示该侧无边界
bool isBST(Node* root, Node* min, Node* max)
{
    if (root == nullptr)
    {
        return true;                       // 空子树永远合格
    }
    if (min != nullptr && root->_key <= min->_key)
    {
        return false;                      // 比下界还小 = 违规
    }
    if (max != nullptr && root->_key >= max->_key)
    {
        return false;                      // 比上界还大 = 违规
    }
    // 深入左子树时，根成为新的上界；深入右子树时，根成为新的下界
    return isBST(root->_left, min, root) && isBST(root->_right, root, max);
}
 
int main()
{
    // 构造一棵合格的 BST：8, 3, 10, 1, 6
    Node* good = new Node(8);
    good->_left = new Node(3);
    good->_right = new Node(10);
    good->_left->_left = new Node(1);
    good->_left->_right = new Node(6);
    std::cout << "good 是 BST 吗？" << (isBST(good, nullptr, nullptr) ? "是" : "否") << std::endl;
 
    // 人为破坏：让左子树里冒出一个大于根的值 9
    Node* bad = new Node(8);
    bad->_left = new Node(3);
    bad->_left->_right = new Node(9);   // 9 > 8，却藏在了根的左子树里
    std::cout << "bad 是 BST 吗？" << (isBST(bad, nullptr, nullptr) ? "是" : "否") << std::endl;
 
    delete good->_left->_left; delete good->_left->_right; delete good->_left;
    delete good->_right; delete good;
    delete bad->_left->_right; delete bad->_left; delete bad;
    return 0;
}

template<class K>
struct BSTNode
{
    K _key;                        // 结点中保存的关键码
    BSTNode<K>* _left;             // 指向左孩子
    BSTNode<K>* _right;            // 指向右孩子
 
    BSTNode(const K& key)          // 构造函数：构造时把两个孩子先置空
        : _key(key)
        , _left(nullptr)
        , _right(nullptr)
    {
    }
};

template<class K>
class BSTree
{
    typedef BSTNode<K> Node;     // 给结点类型起个短别名，方便书写
public:
    void InOrder()               // 对外接口：打印整棵搜索树
    {
        _InOrder(_root);
        std::cout << std::endl;
    }
 
private:
    void _InOrder(Node* root)    // 真正的递归实现
    {
        if (root == nullptr)     // 递归边界：空结点直接返回
        {
            return;
        }
        _InOrder(root->_left);                  // 先访问左子树
        std::cout << root->_key << " ";         // 再打印当前结点
        _InOrder(root->_right);                 // 最后访问右子树
    }
 
    Node* _root = nullptr;       // 这棵树的根节点指针
};

#include <iostream>
#include <utility>     // 提供 std::swap
 
template<class K>
struct BSTNode
{
    K _key;
    BSTNode<K>* _left;
    BSTNode<K>* _right;
    BSTNode(const K& key)
        : _key(key), _left(nullptr), _right(nullptr)
    {}
};
 
template<class K>
class BSTree
{
    typedef BSTNode<K> Node;
public:
    BSTree() = default;                    // 默认构造：_root 用自带默认值 nullptr
 
    BSTree(const BSTree& t)                // 深拷贝构造
        : _root(_Copy(t._root))
    {
    }
 
    BSTree& operator=(BSTree t)            // 赋值：拷贝交换（copy-and-swap）
    {
        std::swap(_root, t._root);         // 换走旧树，旧树随形参 t 析构释放
        return *this;
    }
 
    ~BSTree()                              // 析构：后序释放整棵树
    {
        _Destroy(_root);
    }
 
    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;              // 不允许重复 key
            }
        }
        cur = new Node(key);
        if (parent->_key < key)
            parent->_right = cur;
        else
            parent->_left = cur;
        return true;
    }
 
    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;
    }
 
    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 (parent == nullptr) _root = cur->_right;
                    else if (parent->_left == cur) parent->_left = cur->_right;
                    else parent->_right = cur->_right;
                    delete cur;
                    return true;
                }
                else if (cur->_right == nullptr)  // 右空：左孩子顶上
                {
                    if (parent == nullptr) _root = cur->_left;
                    else if (parent->_left == cur) parent->_left = cur->_left;
                    else parent->_right = cur->_left;
                    delete cur;
                    return true;
                }
                else
                {
                    // 双孩子：用右子树最小结点替换
                    Node* rightMinP = cur;
                    Node* rightMin = cur->_right;
                    while (rightMin->_left)
                    {
                        rightMinP = rightMin;
                        rightMin = rightMin->_left;
                    }
                    cur->_key = rightMin->_key;
                    if (rightMinP->_left == rightMin)
                        rightMinP->_left = rightMin->_right;
                    else
                        rightMinP->_right = rightMin->_right;
                    delete rightMin;
                    return true;
                }
            }
        }
        return false;
    }
 
    void InOrder() { _InOrder(_root); std::cout << std::endl; }
 
private:
    void _InOrder(Node* root)
    {
        if (root == nullptr) return;
        _InOrder(root->_left);
        std::cout << root->_key << " ";
        _InOrder(root->_right);
    }
 
    void _Destroy(Node* root)                // 后序释放整棵树
    {
        if (root == nullptr) return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
 
    Node* _Copy(Node* root)                  // 深拷贝：逐一重建每个结点
    {
        if (root == nullptr) return nullptr;
        Node* newNode = new Node(root->_key);
        newNode->_left = _Copy(root->_left);
        newNode->_right = _Copy(root->_right);
        return newNode;
    }
 
    Node* _root = nullptr;
};
 
int main()
{
    BSTree<int> t;
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    for (int x : a) t.Insert(x);
    t.InOrder();                        // 1 3 4 6 7 8 10 13 14
 
    BSTree<int> copy(t);                // 深拷贝构造：copy 和 t 各自独立
    copy.Erase(8);
    copy.InOrder();                     // 1 3 4 6 7 10 13 14
    t.InOrder();                        // 原树完好不受影响：1 3 4 6 7 8 10 13 14
 
    BSTree<int> assigned;
    assigned = t;                       // 拷贝交换式赋值，同样深拷贝
    assigned.InOrder();                 // 1 3 4 6 7 8 10 13 14
    return 0;                           // 三个对象析构，各自释放自己的树，无泄漏无双重释放
}

bool Find(const K& key)
{
    Node* cur = _root;            // 从根结点开始比较
    while (cur)                   // 一旦 cur 走到空，说明找完了
    {
        if (cur->_key < key)      // 当前值比 key 小，目标是右子树
        {
            cur = cur->_right;
        }
        else if (cur->_key > key) // 当前值比 key 大，目标是左子树
        {
            cur = cur->_left;
        }
        else                      // 相等，找到了
        {
            return true;
        }
    }
    return false;                 // 走到空仍未找到，说明不存在
}

bool FindR(const K& key)
{
    return _FindR(_root, key);    // 入口，传入真正的根
}
 
private:
bool _FindR(Node* root, const K& key)
{
    if (root == nullptr)          // 递归边界：走到空仍然没找到
    {
        return false;
    }
    if (root->_key < key)         // 当前值小，去右子树找
    {
        return _FindR(root->_right, key);
    }
    else if (root->_key > key)    // 当前值大，去左子树找
    {
        return _FindR(root->_left, key);
    }
    else                          // 相等，找到了
    {
        return true;
    }
}

#include <iostream>
 
struct Node
{
    int _key;
    Node* _left = nullptr;
    Node* _right = nullptr;
    explicit Node(int k) : _key(k) {}
};
 
Node* g_root = nullptr;
 
// 支持重复值的插入：相等时统统一律往右走，保持一致性
void Insert(int key)
{
    if (g_root == nullptr)
    {
        g_root = new Node(key);
        return;
    }
    Node* parent = nullptr;
    Node* cur = g_root;
    while (cur)
    {
        parent = cur;
        if (cur->_key <= key)    // “小于等于”都往右：让相等的凑在一起且保持一致
            cur = cur->_right;
        else
            cur = cur->_left;
    }
    if (parent->_key <= key)
        parent->_right = new Node(key);
    else
        parent->_left = new Node(key);
}
 
// 返回中序第一个等于 key 的结点；找不到返回 nullptr
Node* FindFirst(int key)
{
    Node* cur = g_root;
    Node* result = nullptr;
    while (cur)
    {
        if (cur->_key < key)
            cur = cur->_right;
        else if (cur->_key > key)
            cur = cur->_left;
        else
        {
            result = cur;        // 先记下这个相等的结点
            cur = cur->_left;    // 继续向左，寻找更靠前的相等结点
        }
    }
    return result;
}
 
void InOrder(Node* root)
{
    if (!root) return;
    InOrder(root->_left);
    std::cout << root->_key << " ";
    InOrder(root->_right);
}
 
int main()
{
    int a[] = { 5, 3, 5, 7, 5, 3, 9 };
    for (int x : a) Insert(x);
    InOrder(g_root);             // 输出：3 3 5 5 5 7 9（值相等但有序，去重不去序）
    std::cout << std::endl;
 
    Node* f = FindFirst(5);
    std::cout << (f ? "找到中序第一个 5" : "未找到 5") << std::endl;
    return 0;                    // 释放逻辑未在 demo 展开，请勿用于生产，重点看查找思路
}

// 错误写法（示意，请勿运行）：cur 只是地址的拷贝，改它改不到树
Node* cur = _root;
while (cur)
{
    if (cur->_key < key) cur = cur->_right;
    else if (cur->_key > key) cur = cur->_left;
    else return false;   // 重复，返回失败
}
cur = new Node(key);     // 只改局部的"纸条"，树的对应孩子指针仍是原来的空指针！

bool Insert(const K& key)
{
    // 情况一：树为空，直接让根指向新结点
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }
 
    // 情况二：树不空，先找空位，同时记下父结点
    Node* parent = nullptr;       // 记录 cur 的父结点，用于最后挂接
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key < key)      // 目标更大，往右走，先更新 parent 再前进
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key) // 目标更小，往左走
        {
            parent = cur;
            cur = cur->_left;
        }
        else                      // 相等：本实现不允许重复值，直接返回失败
        {
            return false;
        }
    }
 
    // 找到空位，创建新结点，挂到 parent 的正确一侧
    cur = new Node(key);
    if (parent->_key < key)       // 新值比父节点大，挂右边
    {
        parent->_right = cur;
    }
    else                          // 否则挂左边
    {
        parent->_left = cur;
    }
    return true;
}

#include <iostream>
 
// 假设上面那颗完整的 BSTree<int> 类定义在此（含 Insert/Find/Erase/InOrder/析构/拷贝）
// 为聚焦插入验证，此处用同接口的最简版亦可
int main()
{
    BSTree<int> tree;                        // 一棵只存 int 的搜索树
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };  // 课件经典数组
    for (int x : a)                          // 依次插入每个元素
    {
        tree.Insert(x);
    }
 
    tree.InOrder();                          // 中序遍历打印
    return 0;
}

bool InsertR(const K& key)
{
    return _InsertR(_root, key);   // 入口，注意这里要传引用
}
 
private:
bool _InsertR(Node*& root, const K& key)   // root 是引用，才能原地修改指针
{
    if (root == nullptr)                   // 递归边界：到达空位
    {
        root = new Node(key);              // 因为 root 是引用，直接挂接成功
        return true;
    }
    if (root->_key < key)                  // 目标更大，往右子树插
    {
        return _InsertR(root->_right, key);
    }
    else if (root->_key > key)             // 目标更小，往左子树插
    {
        return _InsertR(root->_left, key);
    }
    else                                   // 重复值，返回失败
    {
        return false;
    }
}

bool Erase(const K& key)
{
    Node* parent = nullptr;      // 记录当前结点的父节点
    Node* cur = _root;           // 从根开始找要删的结点
    while (cur)
    {
        if (cur->_key < key)     // 目标更大，向右找，并同步更新 parent
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key) // 目标更小，向左找
        {
            parent = cur;
            cur = cur->_left;
        }
        else                      // 找到了，进入删除逻辑
        {
            // ====== 情况①②：N 最多一个孩子，采用"顶替法" ======
            if (cur->_left == nullptr)      // 左孩子为空：用右孩子顶上来
            {
                if (parent == nullptr)      // N 是根：直接把根换成右孩子
                {
                    _root = cur->_right;
                }
                else if (parent->_left == cur)   // N 是父节点的左孩子
                {
                    parent->_left = cur->_right;
                }
                else                            // N 是父节点的右孩子
                {
                    parent->_right = cur->_right;
                }
                delete cur;                 // 释放 N 的内存
                return true;
            }
            else if (cur->_right == nullptr) // 右孩子为空：用左孩子顶上来
            {
                if (parent == nullptr)      // N 是根：直接把根换成左孩子
                {
                    _root = cur->_left;
                }
                else if (parent->_left == cur)
                {
                    parent->_left = cur->_left;
                }
                else
                {
                    parent->_right = cur->_left;
                }
                delete cur;                 // 释放 N 的内存
                return true;
            }
            else
            {
                // ====== 情况③：N 有两个孩子，采用"替换法"删除 ======
                // 思路：找右子树最小结点（或左子树最大结点）顶替 N，再删掉替身
                Node* rightMinP = cur;                 // 替身的父节点，必须先初始化为 cur
                Node* rightMin = cur->_right;          // 从右孩子的根开始找右子树最小
                while (rightMin->_left)                // 一路向左走到底，即右子树最小值
                {
                    rightMinP = rightMin;
                    rightMin = rightMin->_left;
                }
 
                cur->_key = rightMin->_key;            // 第一步：把替身的值赋给 N
 
                // 第二步：删除替身（它最多只有一个右孩子，属于前面两种情况）
                if (rightMinP->_left == rightMin)      // 替身是父节点的左孩子
                {
                    rightMinP->_left = rightMin->_right;
                }
                else                                   // 替身是父节点的右孩子（右子树根即最小）
                {
                    rightMinP->_right = rightMin->_right;
                }
                delete rightMin;                       // 释放替身的内存
                return true;
            }
        }
    }
    return false;                // 树里没有这个 key，删除失败
}

else     // 情况③：N 有两个孩子，替换法删除
{
    Node* rightMinP = cur;   // 替身的父节点，这里必须先初始化为 cur
    Node* rightMin = cur->_right;  // 从右孩子的根开始，去找右子树的最小结点
    while (rightMin->_left)          // 一路向左走到底，就是右子树最小结点
    {
        rightMinP = rightMin;
        rightMin = rightMin->_left;
    }
 
    cur->_key = rightMin->_key;      // 第一步：把最小结点的值赋给 N（替换）
 
    // 第二步：删除最小结点（它最多只有一个右孩子，属于情况①②）
    if (rightMinP->_left == rightMin)   // 最小结点是父节点的左孩子
    {
        rightMinP->_left = rightMin->_right;   // 用它的右孩子顶上
    }
    else                                  // 最小结点是父节点的右孩子（即它就是右孩子本身）
    {
        rightMinP->_right = rightMin->_right;
    }
    delete rightMin;                // 释放最小结点的内存
    return true;
}

else     // 情况③的对称实现：用左子树最大结点替换（与右最小版原理完全相同）
{
    Node* leftMaxP = cur;             // 替身父节点，先记为 cur
    Node* leftMax = cur->_left;       // 从左孩子的根开始，向右找左子树最大
    while (leftMax->_right)           // 一路向右走到底，就是左子树最大结点
    {
        leftMaxP = leftMax;
        leftMax = leftMax->_right;
    }
 
    cur->_key = leftMax->_key;        // 值替换
 
    // 删除替身：最大结点最多只有一个左孩子
    if (leftMaxP->_right == leftMax)
        leftMaxP->_right = leftMax->_left;   // 正常情况下它来自右链
    else
        leftMaxP->_left = leftMax->_left;    // 左子树根本身就是最大，走左分支
    delete leftMax;
    return true;
}

#include <iostream>
 
// 假设上面那颗完整 BSTree<int> 类定义在此（含 Insert/Find/Erase/InOrder/析构/拷贝）
int main()
{
    BSTree<int> tree;
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
    for (int x : a)
    {
        tree.Insert(x);
    }
 
    tree.InOrder();               // 初始：1 3 4 6 7 8 10 13 14
 
    tree.Erase(1);                // 叶子结点，直接删
    tree.InOrder();               // 3 4 6 7 8 10 13 14
 
    tree.Erase(3);                // 单孩子结点（它的右孩子顶上来）
    tree.InOrder();               // 4 6 7 8 10 13 14
 
    tree.Erase(8);                // 双孩子结点，用右子树最小结点替换
    tree.InOrder();               // 观察：8 被 10 替换后，结果仍有序
 
    std::cout << (tree.Find(8) ? "8 存在" : "8 已删除") << std::endl;
 
    return 0;
}

#include <iostream>
 
// 假设上面那颗完整 BSTree<int> 类定义在此（含 Insert/Find/Erase/InOrder/析构/拷贝）
int main()
{
    BSTree<int> tree;
    for (int x : { 9, 5, 12, 3, 7, 11, 15 })
    {
        tree.Insert(x);            // 乱序插入
    }
    tree.InOrder();                // 输出：3 5 7 9 11 12 15，天然有序
 
    std::cout << (tree.Find(7) ? "7 在" : "7 不在") << std::endl;     // 在
    std::cout << (tree.Find(8) ? "8 在" : "8 不在") << std::endl;     // 不在
 
    tree.Erase(7);                 // 删除单孩子结点
    tree.Erase(9);                 // 删除双孩子结点（右子树最小 11 替换）
    tree.InOrder();                // 输出：3 5 11 12 15
    return 0;
}

template<class K, class V>
struct BSTNode
{
    K _key;                     // 关键码（用于比较、决定树结构）
    V _value;                   // 与 key 绑定的值（可以任意类型）
    BSTNode<K, V>* _left;       // 左孩子
    BSTNode<K, V>* _right;      // 右孩子
 
    BSTNode(const K& key, const V& value)
        : _key(key)
        , _value(value)
        , _left(nullptr)
        , _right(nullptr)
    {
    }
};

#include <iostream>
#include <string>
using namespace std;
 
class BSTreeKV   // key/value 版搜索树
{
    struct Node
    {
        string _key;    // 关键码：这里用 string
        int _value;     // 与 key 绑定的值：这里用 int
        Node* _left;
        Node* _right;
        Node(const string& key, int value)
            : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
    };
    Node* _root = nullptr;
 
public:
    ~BSTreeKV() { _Destroy(_root); }     // 析构：后序释放整棵树，避免内存泄漏
 
    bool Insert(const string& key, int 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                           // 重复 key 不允许插入
            {
                return false;
            }
        }
        cur = new Node(key, value);        // 找到空位后挂接
        if (parent->_key < key)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        return true;
    }
 
    Node* Find(const string& key)          // 修改：返回结点而非 bool，好用 value
    {
        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;
    }
 
    void InOrder() { _InOrder(_root); cout << endl; }
 
private:
    void _InOrder(Node* root)
    {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << ":" << root->_value << endl;  // 打印 key 与 value
        _InOrder(root->_right);
    }
 
    void _Destroy(Node* root)              // 后序释放整棵树
    {
        if (root == nullptr) return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
};
 
int main()
{
    // ---- 场景1：词频统计 ----
    BSTreeKV countTree;
    string words[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    for (const string& w : words)
    {
        auto ret = countTree.Find(w);       // 先查这个单词是否出现过
        if (ret == nullptr)                 // 第一次出现：插入（词, 1）
        {
            countTree.Insert(w, 1);
        }
        else                                // 出现过：次数加一
        {
            ret->_value++;
        }
    }
    cout << "单词出现次数：" << endl;
    countTree.InOrder();                    // 每个词连同次数有序输出
 
    cout << endl;
    // ---- 场景2：简易英中词典 ----
    BSTreeKV dict;
    dict.Insert("left", 0);
    dict.Insert("right", 0);
    string word = "left";
    auto it = dict.Find(word);
    if (it != nullptr)
    {
        std::cout << "查出 left 并取其 value=" << it->_value << endl;
    }
    return 0;
}

#include <iostream>
 
// 假设上面那颗完整 BSTree<int> 类定义在此（含 Insert/Find/Erase/InOrder/析构/拷贝）
int main()
{
    BSTree<int> balanced;
    int mid[] = { 50, 25, 75, 12, 37, 62, 88 };   // 尽量居中的插入顺序
    for (int x : mid)
    {
        balanced.Insert(x);
    }
 
    BSTree<int> degenerate;
    int ordered[] = { 12, 25, 37, 50, 62, 75, 88 }; // 有序插入
    for (int x : ordered)
    {
        degenerate.Insert(x);
    }
 
    std::cout << "有序插入后中序遍历（仍是升序，但树早已畸形成链）:" << std::endl;
    degenerate.InOrder();
    return 0;
}