导航：首页 > 互联网科技 >

如何删除二叉树中的节点

发表于：2025-01-31 作者：千家信息网编辑

千家信息网最后更新 2025年01月31日，如何删除二叉树中的节点，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。算法：1.后驱算法：/*递归解法：1.找到需要删除的节点2.删除的节

千家信息网最后更新 2025年01月31日如何删除二叉树中的节点

如何删除二叉树中的节点，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

算法：

1.后驱算法：

/*递归解法：1.找到需要删除的节点2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，或者将右子树的最小节点也就称作后驱当作删除节点。*/

2.前驱算法：

/*递归解法：1.找到需要删除的节点2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，或者将右子树的最小节点也就称作后驱当作删除节点。*/

题目：

后驱算法：

func deleteNode(root *TreeNode, key int) *TreeNode {    if root == nil {        return nil    }    if key < root.Val {        root.Left = deleteNode(root.Left,key)        return root    }    if key > root.Val {        root.Right = deleteNode(root.Right,key)        return root    }    // 这里通过递归已经找到了要删除的节点,此时因为递归的原因还是root这个指针    if root.Right == nil {        return root.Left    }    if root.Left == nil {        return root.Right    }    // 后驱的方法来替换当前节点    min := root.Right    for min.Left != nil {        min = min.Left    }    root.Val = min.Val // 替换需要删除的节点的数值，这里就是复制    root.Right = deleteMin(root.Right) // 这里把右子树中移动过来的那个最小节点删除掉    return root}func deleteMin(root *TreeNode) *TreeNode{    // 左子树不在的话，表示这个节点就是要删除的最小节点    // 存在两种情况，一：这个节点就是叶子节点，直接通过赋值为nil, 来当作删除节点。    // 二：这个节点没有左子树，只有右子树，这样的话，需要将右子树替换成该节点    if root.Left == nil {         right := root.Right        root.Right = nil         return right    }    root.Left = deleteMin(root.Left) // 左子树一直在的话，就一直通过左子树去找最小节点    return root}

前驱算法

func deleteNode(root *TreeNode, key int) *TreeNode {    if root == nil {        return nil    }    if key < root.Val {        root.Left = deleteNode(root.Left,key)        return root    }    if key > root.Val {        root.Right = deleteNode(root.Right,key)        return root    }    // 这里通过递归已经找到了要删除的节点,此时因为递归的原因还是root这个指针    if root.Right == nil {        return root.Left    }    if root.Left == nil {        return root.Right    }    // 前驱的方法来替换当前节点    max := root.Left    for max.Right != nil {        max = max.Right    }    root.Val = max.Val    root.Left = deleteMax(root.Left)    return root}
func deleteMax(root *TreeNode) *TreeNode {    if root.Right == nil {        left := root.Left        root.Left = nil         return left    }    root.Right = deleteMax(root.Right)    return root}/*递归解法：1.找到需要删除的节点2.删除的节点只有右子树或者左子树，直接将右子树或者左子树的根节点当作这个删除的节点3.删除的节点左右子树都存在的情况下，左子树的最大节点也叫做前驱当作删除节点，或者将右子树的最小节点也就称作后驱当作删除节点。*/