刪除BST節點有兩個孩子時

我想刪除BST中有兩個子節點的節點。例如，刪除BST節點有兩個孩子時

我想刪除包含info = 12的節點。我需要幫助來執行此操作。

2012-12-05 mumair

這是功課？你有什麼嘗試？ – atoMerz

所以哪一個呢？ Java，C或C++？ –

將數據從包含6的節點移動到包含12的節點，用12覆蓋12。刪除包含6的葉節點。 –

您需要獲取其左子樹的最右側子元素，或者右子樹的最左側子元素（例如6或15），並將其中一個移動到該位置，那麼你可以刪除你想要的節點。

如果您正在做任何事情來跟蹤子樹中的節點數量，您通常希望從較大的子樹中選取節點，因此當您移動它時，樹會至少平衡，因爲它開始。例如，在這種情況下，獲得6比15來保持平衡更好 - 但是如果你只是有一個普通的，不平衡的BST，那麼你可能沒有那種容易獲得的信息。

2012-12-05 05:22:41

有這樣的算法第4版的圖書網站商量好了：http://algs4.cs.princeton.edu/32bst/

2012-12-05 05:27:59 udeleng

回答