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

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

冰火之心

发布： 2025-10-03 16:52:02

原创

949人浏览过

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

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

在C++中删除二叉搜索树（BST）中的节点需要根据节点的子节点情况分三种情形处理，同时保持BST的性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点。

删除节点的三种情况

假设要删除的节点为 node，其子节点情况如下：

没有子节点（叶子节点）：直接删除，将其父节点对应指针置为 nullptr。
只有一个子节点：用其子节点替代该节点位置。
有两个子节点：找到其中序后继（右子树中的最小节点）或中序前驱（左子树中的最大节点），用该节点的值替换当前节点的值，然后删除那个后继或前驱节点（它最多只有一个右子节点）。

节点结构定义

// 定义二叉树节点 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

查找最小值节点（用于找中序后继）

TreeNode* findMin(TreeNode* root) { while (root->left != nullptr) { root = root->left; } return root; }

这个函数用于找到某个子树中的最小节点，通常用来找右子树的最左节点（即中序后继）。

删除节点的实现

TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr;

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 && !root->right) {
        // 情况1：无子节点
        delete root;
        return nullptr;
    } else if (!root->left) {
        // 情况2：只有右子节点
        TreeNode* temp = root->right;
        delete root;
        return temp;
    } else if (!root->right) {
        // 情况2：只有左子节点
        TreeNode* temp = root->left;
        delete root;
        return temp;
    } else {
        // 情况3：两个子节点
        TreeNode* successor = findMin(root->right);
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
}
return root;

登录后复制

}

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

这段代码使用递归方式实现删除操作。当找到目标节点后，按上述三种情况分别处理。对于有两个子节点的情况，采用中序后继法进行替换删除。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

使用示例

int main() { TreeNode* root = new TreeNode(5); root->left = new TreeNode(3); root->right = new TreeNode(7); root->left->left = new TreeNode(2); root->left->right = new TreeNode(4); root->right->left = new TreeNode(6); root->right->right = new TreeNode(8);

root = deleteNode(root, 3);  // 删除节点3

return 0;

登录后复制

}

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

删除节点3后，会用其右子树的最小节点4替代，树的结构依然满足BST性质。

基本上就这些。只要理清三种删除情况，尤其是双子节点时用后继节点替换的思想，就能正确实现BST的删除操作。注意内存释放和指针更新的顺序，避免悬空指针或内存泄漏。

以上就是c++++中如何在二叉搜索树中删除节点_c++二叉搜索树删除节点方法的详细内容，更多请关注php中文网其它相关文章！

大家都在看：

如何配置C++的AI推理框架环境 TensorRT加速库安装使用 C++与AI部署：ONNX Runtime集成全解析 C++中的SFINAE技术是怎么回事_C++模板编程与SFINAE机制解析 c++指针是什么意思_c++指针概念与基本用法解析 c++怎么用libtorch加载一个PyTorch模型_C++深度学习模型加载与libtorch实践