C++從當節點有兩個孩子

假設我有一棵樹如下樹刪除節點：C++從當節點有兩個孩子

如果我想刪除3，用最低的左節點替換它（在這種情況下， 1）。 2將附加到4，在該圖中。

我該如何編碼？

我知道你必須繼續遍歷一些循環，然後重新設置每個指針。此外，您必須考慮最後一個左節點可能有正確子節點的情況。

來源

2012-06-07 forthewinwin

您嘗試過什麼？你應該明白，我們不是在這裏做你的功課：http://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions – chembrad

你不*要*下降到最左邊的節點。您需要左子樹的最右端節點或右子樹的最左端節點。由於'1'和'2'都下降到'4'的* left *，所以你可以提升'4'來代替'3'，而不是'1'（如果你把'1'移到上面，那麼搜索樹將不再有效（它的左後代會比它更大，違反了樹的基本規則） –

@JerryCoffin：樹已經失序，當我讀它時，遍歷是1 2 4 3 5 8 6 12 15 – jxh

我們解決之前，「怎麼做」，兩件事情：

（1） - 這是次要的。這個問題僅在二進制搜索樹（BST）的背景下才有意義，而不僅僅是一個二叉樹。而且這棵樹不是BST，因爲3和4是交換的。（2） - 任何時候你在BST上執行刪除操作，並且你想「修復」樹使得生成的樹也是BST，你有兩種選擇：（a）你可以選擇（b）您可以選擇要刪除的節點的右側子樹中的最小值，然後將其與要刪除的節點進行交換。（你應該說服自己，爲什麼這些選項都會讓你成爲BST）。在你的例子中（正確放置3和4），這意味着將4與3或5交換。

現在爲「如何」做到這一點。假設我們從上面選擇了選項（a）。你需要做的是編寫一個函數，從4開始，將會走一步，然後儘可能長地遍歷（你也應該說服自己爲什麼這是正確的）。一旦你不能再遍歷到右邊，你知道你已經在左子樹中找到了最大的值。然後，將該值替換爲要刪除的節點，然後刪除剛剛取得的節點值。

如果你已經想出瞭如何對你在這裏展示的樹進行編碼，這實際上很簡單。如果您有特定代碼問題，請提供更多詳細信息

來源

2012-08-21 23:52:22

C++從當節點有兩個孩子

回答

相關問題