c/c++中的二叉树进阶

c23856

266人浏览 · 2026-06-03 08:46:43

c23856 · 2026-06-03 08:46:43 发布

1. 二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）也叫二叉排序树，是最基础的有序树形结构，C++ std::map 的底层雏形（标准库用红黑树 = 平衡版 BST），核心特点：有序、快速查找、插入、删除。

1.核心性质

满足4 条铁律，就是二叉搜索树：
1.左子树的所有节点值 < 根节点值
2.右子树的所有节点值 > 根节点值
3.左、右子树也必须是二叉搜索树
4.中序遍历结果 = 升序有序序列（最核心特性！）
无重复节点值（和 map 的 key 唯一一致）

这就是一颗标准的二叉搜索树：

中序遍历：2 → 3 → 4 → 5 → 6 → 7 → 8（严格升序）

2.、三大核心操作

1. 查找操作

规则：
值 < 根 → 查左子树
值 > 根 → 查右子树
值 = 根 → 找到
到空节点 → 没找到

// 递归查找
Node* search(Node* root, int target) {
    // 空树/没找到
    if (root == nullptr) return nullptr;
    // 找到目标
    if (root->val == target) return root;
    // 目标更小，查左子树
    if (target < root->val) return search(root->left, target);
    // 目标更大，查右子树
    else return search(root->right, target);
}

2.插入操作

规则：查找的过程中，找到空位置直接插入，保证有序。
插入后依然满足 BST 性质
重复值不插入（保持唯一）

// 递归插入
Node* insert(Node* root, int val) {
    // 找到空位置，创建新节点
    if (root == nullptr) return new Node(val);
    
    // 值已存在，不插入
    if (val == root->val) return root;
    
    // 值更小，插入左子树
    if (val < root->val) root->left = insert(root->left, val);
    // 值更大，插入右子树
    else root->right = insert(root->right, val);
    
    return root;
}

3. 删除操作

删除后必须保持 BST 有序，分三种场景：
情况 1：删除叶子节点（无孩子）
直接删除，置空即可。
例：删除 2、4、6、8
情况 2：删除只有一个孩子的节点
用孩子节点替代被删节点。
例：删除只有左 / 右孩子的节点
情况 3：删除有两个孩子的节点（核心）
找后继节点（右子树的最小值）替代，再删除后继节点。
例：删除根节点 5 → 用 6 替代

// 找右子树的最小值（后继节点）
Node* getMin(Node* node) {
    while (node->left) node = node->left;
    return node;
}

// 递归删除节点
Node* remove(Node* root, int val) {
    if (root == nullptr) return nullptr;

    // 查找要删除的节点
    if (val < root->val) root->left = remove(root->left, val);
    else if (val > root->val) root->right = remove(root->right, val);
    // 找到待删除节点
    else {
        // 情况1：无孩子（叶子节点）
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // 情况2：只有一个孩子
        else if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        // 情况3：两个孩子 → 找右子树最小值替代
        else {
            Node* minNode = getMin(root->right);
            root->val = minNode->val;                // 替换值
            root->right = remove(root->right, minNode->val); // 删除后继节点
        }
    }
    return root;
}