溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

如何刪除二叉樹中的節(jié)點(diǎn)

發(fā)布時(shí)間：2021-11-20 09:30:11 來源：億速云 閱讀：427 作者：柒染 欄目：大數(shù)據(jù)

如何刪除二叉樹中的節(jié)點(diǎn)，相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

算法：

1.后驅(qū)算法：

/*遞歸解法：1.找到需要?jiǎng)h除的節(jié)點(diǎn)2.刪除的節(jié)點(diǎn)只有右子樹或者左子樹，直接將右子樹或者左子樹的根節(jié)點(diǎn)當(dāng)作這個(gè)刪除的節(jié)點(diǎn)3.刪除的節(jié)點(diǎn)左右子樹都存在的情況下，左子樹的最大節(jié)點(diǎn)也叫做前驅(qū)當(dāng)作刪除節(jié)點(diǎn)，或者將右子樹的最小節(jié)點(diǎn)也就稱作后驅(qū)當(dāng)作刪除節(jié)點(diǎn)。*/

2.前驅(qū)算法：

/*遞歸解法：1.找到需要?jiǎng)h除的節(jié)點(diǎn)2.刪除的節(jié)點(diǎn)只有右子樹或者左子樹，直接將右子樹或者左子樹的根節(jié)點(diǎn)當(dāng)作這個(gè)刪除的節(jié)點(diǎn)3.刪除的節(jié)點(diǎn)左右子樹都存在的情況下，左子樹的最大節(jié)點(diǎn)也叫做前驅(qū)當(dāng)作刪除節(jié)點(diǎn)，或者將右子樹的最小節(jié)點(diǎn)也就稱作后驅(qū)當(dāng)作刪除節(jié)點(diǎn)。*/

題目：

如何刪除二叉樹中的節(jié)點(diǎn)

后驅(qū)算法：

如何刪除二叉樹中的節(jié)點(diǎn)

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    }    // 這里通過遞歸已經(jīng)找到了要?jiǎng)h除的節(jié)點(diǎn),此時(shí)因?yàn)檫f歸的原因還是root這個(gè)指針    if root.Right == nil {        return root.Left    }    if root.Left == nil {        return root.Right    }    // 后驅(qū)的方法來替換當(dāng)前節(jié)點(diǎn)    min := root.Right    for min.Left != nil {        min = min.Left    }    root.Val = min.Val // 替換需要?jiǎng)h除的節(jié)點(diǎn)的數(shù)值，這里就是復(fù)制    root.Right = deleteMin(root.Right) // 這里把右子樹中移動(dòng)過來的那個(gè)最小節(jié)點(diǎn)刪除掉    return root}func deleteMin(root *TreeNode) *TreeNode{    // 左子樹不在的話，表示這個(gè)節(jié)點(diǎn)就是要?jiǎng)h除的最小節(jié)點(diǎn)    // 存在兩種情況，一：這個(gè)節(jié)點(diǎn)就是葉子節(jié)點(diǎn)，直接通過賦值為nil, 來當(dāng)作刪除節(jié)點(diǎn)。    // 二：這個(gè)節(jié)點(diǎn)沒有左子樹，只有右子樹，這樣的話，需要將右子樹替換成該節(jié)點(diǎn)    if root.Left == nil {         right := root.Right        root.Right = nil         return right    }    root.Left = deleteMin(root.Left) // 左子樹一直在的話，就一直通過左子樹去找最小節(jié)點(diǎn)    return root}

前驅(qū)算法

如何刪除二叉樹中的節(jié)點(diǎn)

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    }    // 這里通過遞歸已經(jīng)找到了要?jiǎng)h除的節(jié)點(diǎn),此時(shí)因?yàn)檫f歸的原因還是root這個(gè)指針    if root.Right == nil {        return root.Left    }    if root.Left == nil {        return root.Right    }    // 前驅(qū)的方法來替換當(dāng)前節(jié)點(diǎn)    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.找到需要?jiǎng)h除的節(jié)點(diǎn)2.刪除的節(jié)點(diǎn)只有右子樹或者左子樹，直接將右子樹或者左子樹的根節(jié)點(diǎn)當(dāng)作這個(gè)刪除的節(jié)點(diǎn)3.刪除的節(jié)點(diǎn)左右子樹都存在的情況下，左子樹的最大節(jié)點(diǎn)也叫做前驅(qū)當(dāng)作刪除節(jié)點(diǎn)，或者將右子樹的最小節(jié)點(diǎn)也就稱作后驅(qū)當(dāng)作刪除節(jié)點(diǎn)。*/

看完上述內(nèi)容，你們掌握如何刪除二叉樹中的節(jié)點(diǎn)的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手