刪除一個子節點的二叉樹

Question

我在BST刪除一個子節點的情況下有一個非常簡單的問題。

我想檢查的情況下，我的根有一個孩子，但孩子有兩個子節點。它是否應該移除整棵樹？

對於如我有

 5 
    /
    6 
/\ 
    9 10 

如果我不刪除（5）。應該刪除整個樹，因爲5只有一個孩子，即6個，而6個又有兩個子節點。 6也應該只有一個孩子，或者我們不在乎刪除根節點5時有多少個子節點6有一個孩子的狀況

Answer 1

刪除二叉樹的一個節點只有在三種情況，

• 刪除葉節點[節點沒有子]
• 刪除節點與1名兒童
• 刪除節點有兩個孩子

刪除葉節點，只需釋放節點空間並使父節點的子節點鏈接爲空。

用1個孩子刪除節點刪除節點，並將孫子作爲其子。

 10 
    /\ 
    5 15 
/ \ 
    2  17 
/\ 
1 3 

這裏，如果我們想刪除5，使2爲10的孩子，所以樹變得

 10 
    /\ 
    2 15 
/\ \ 
    1 3 17 

這也適用於從樹中刪除15。

http://webdocs.cs.ualberta.ca/~holte/T26/del-from-bst.html

Answer 2

當一個節點只有一個孩子時，我的二叉搜索樹（你不是一個） ，您可以將其移除並將其孩子移植到它的位置（無論孩子的子樹是什麼），同時保留二叉搜索樹屬性。這裏有一個例子：

 7 
    /\ 
    5 9 
/
    3 
/\ 
1 4 

然後如果我刪除了5，並通過其唯一的子樹代替它，我得到

7 
/\ 
    3 9 
/\ 
1 4 

仍然是BST。