如何刪除一棵普通二叉樹(shù)的葉子結(jié)點(diǎn)？首先要知道要?jiǎng)h除的子節(jié)點(diǎn)的地址和父節(jié)點(diǎn)的地址。父節(jié)點(diǎn)的地址應(yīng)該存儲(chǔ)在樹(shù)構(gòu)建過(guò)程中。此時(shí)，二叉樹(shù)的節(jié)點(diǎn)應(yīng)該有三個(gè)指針：指向左子節(jié)點(diǎn)的指針、指向右子節(jié)點(diǎn)的指針和指向父節(jié)點(diǎn)

如何刪除一棵普通二叉樹(shù)的葉子結(jié)點(diǎn)？

首先要知道要?jiǎng)h除的子節(jié)點(diǎn)的地址和父節(jié)點(diǎn)的地址。父節(jié)點(diǎn)的地址應(yīng)該存儲(chǔ)在樹(shù)構(gòu)建過(guò)程中。此時(shí)，二叉樹(shù)的節(jié)點(diǎn)應(yīng)該有三個(gè)指針：指向左子節(jié)點(diǎn)的指針、指向右子節(jié)點(diǎn)的指針和指向父節(jié)點(diǎn)的指針（定義結(jié)構(gòu)時(shí)請(qǐng)注意）。找到父節(jié)點(diǎn)時(shí)，葉節(jié)點(diǎn)的地址用于確定該葉節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)。如果是左子節(jié)點(diǎn)，則父節(jié)點(diǎn)到左子節(jié)點(diǎn)的指針值設(shè)置為null，否則父節(jié)點(diǎn)到右子節(jié)點(diǎn)的指針值設(shè)置為null。然后我們可以釋放要?jiǎng)h除的葉節(jié)點(diǎn)。這是刪除的基本思想。建議建立二叉樹(shù)并用代碼實(shí)現(xiàn)。

為什么刪除二叉排序樹(shù)中一個(gè)結(jié)點(diǎn),再重新插入上去,不一定得到原來(lái)的二叉排序樹(shù)？

二進(jìn)制排序樹(shù)只要求每個(gè)節(jié)點(diǎn)的左子級(jí)小于它，右子級(jí)大于或等于它。先看刪除操作：“先將刪除的節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換，交換后刪除最后一個(gè)節(jié)點(diǎn)，然后重建二叉樹(shù)”，在這個(gè)過(guò)程中，如果刪除根節(jié)點(diǎn)左側(cè)的節(jié)點(diǎn)，則在與最后一個(gè)節(jié)點(diǎn)交換后，為了保持二叉排序樹(shù)的特性，最后一個(gè)節(jié)點(diǎn)會(huì)逐漸向上移動(dòng)，這很可能會(huì)改變根節(jié)點(diǎn)的位置。然后讓我們看看插入操作：“直接與根節(jié)點(diǎn)比較。如果小于根節(jié)點(diǎn)，插入左子樹(shù)，遞歸一次，選擇合適的節(jié)點(diǎn)，如果大于根節(jié)點(diǎn)，依此類(lèi)推。所以平衡二叉樹(shù)可能不同。我建議你畫(huà)一幅圖，試著操作一下，加深對(duì)這兩種操作的理解！