c++中如何在二叉搜索树删除节点_c++二叉搜索树删除节点方法-C++-PHP中文网

c++中如何在二叉搜索树删除节点_c++二叉搜索树删除节点方法

尼克

发布： 2025-10-28 15:45:01

原创

972人浏览过

删除二叉搜索树节点需分三种情况处理：1. 无子节点则直接删除；2. 仅一个子节点时用其替代；3. 有两个子节点则用右子树最小值（中序后继）替换并递归删除该值，确保BST性质不变。

c++中如何在二叉搜索树删除节点_c++二叉搜索树删除节点方法

在C++中删除二叉搜索树（BST）中的节点是一个经典问题，需要根据节点的子节点情况分类处理。核心原则是保持BST的性质：左子树所有值小于根，右子树所有值大于根。

删除节点的三种情况

假设要删除的节点为 target，处理方式如下：

无子节点（叶子节点）：直接删除，父节点对应指针置空。
只有一个子节点：用子节点替代当前节点。
有两个子节点：找到右子树中的最小值（中序后继），用其值替换当前节点值，然后删除那个最小节点。

节点结构定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

删除操作实现

使用递归方式实现删除函数：

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
<pre class='brush:php;toolbar:false;'>if (key < root->val) {
    root->left = deleteNode(root->left, key);
} else if (key > root->val) {
    root->right = deleteNode(root->right, key);
} else {
    // 找到目标节点，开始删除
    if (!root->left) {
        TreeNode* temp = root->right;
        delete root;
        return temp;
    } else if (!root->right) {
        TreeNode* temp = root->left;
        delete root;
        return temp;
    }

    // 有两个子节点：找右子树的最小节点（中序后继）
    TreeNode* minNode = root->right;
    while (minNode->left) {
        minNode = minNode->left;
    }
    root->val = minNode->val; // 替换值
    root->right = deleteNode(root->right, minNode->val); // 删除后继
}
return root;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；