愛華網(wǎng)對(duì)刪除來說，我們考慮包含被刪除元素的節(jié)點(diǎn)p 的三種情況：1) p 是樹葉；2) p 只有一個(gè)
非空子樹；3) p 有兩個(gè)非空子樹。
情況1) 可以用丟棄樹葉節(jié)點(diǎn)的方法來處理。要?jiǎng)h除圖11-3b 所示樹中的3 5，只要把其父節(jié)
點(diǎn)的左孩子域置為零，然后刪除該節(jié)點(diǎn)即可，刪除后結(jié)果如圖 11-3a 所示。要從樹中刪除8 0，
只要把節(jié)點(diǎn)4 0的右孩子域置為零并丟棄節(jié)點(diǎn)8 0，其結(jié)果如圖11-1b 所示。
接下來考察情況2 )。如果p 沒有父節(jié)點(diǎn)（即p 是根節(jié)點(diǎn)） ，則將p 丟棄，p 的唯一子樹的根
節(jié)點(diǎn)成為新的搜索樹的根節(jié)點(diǎn)。如果p 有父節(jié)點(diǎn)p p，則修改pp 的指針，使得pp 指向p 的唯一孩
子，然后刪除節(jié)點(diǎn)p。例如，如果希望從圖11-3b 的樹中刪除關(guān)鍵值為5的元素，則修改該元素
父節(jié)點(diǎn)的左孩子域，使其指向關(guān)鍵值為2的節(jié)點(diǎn)。
最后，要?jiǎng)h除一個(gè)左右子樹都不為空的節(jié)點(diǎn)中的元素，只需將該元素替換為它的左子樹中
的最大元素或右子樹中的最小元素。假設(shè)希望刪除圖 11-4a 中關(guān)鍵值為4 0的元素，那么既可以
用它左子樹中的最大元素( 3 5 )，也可以用它右子樹中的最小元素（6 0）來替換它。如果選擇右
子樹中的最小元素，那么把關(guān)鍵值為6 0的元素移到4 0被刪除的位置，再把原來的葉節(jié)點(diǎn)6 0刪除
即可。結(jié)果如圖11-4b 所示。
假定用左子樹中的最大元素來代替被刪除的元素4 0。左子樹中的最大元素是3 5，且只有一
個(gè)子女，把3 5移到4 0的節(jié)點(diǎn)中，將其左孩子指向原來節(jié)點(diǎn)3 5的唯一子女，結(jié)果如圖11-4c 所示。
再來看另一個(gè)例子，刪除圖11-4c 中的節(jié)點(diǎn)3 0。既可以用5，也可以用3 1來替換節(jié)點(diǎn)3 0。如
果選用5，而5是只有一個(gè)孩子的節(jié)點(diǎn)，那么只要把其左孩子域指向 5原來的唯一子女即可，結(jié)
3 2 4 第二部分 數(shù) 據(jù) 結(jié) 構(gòu)
下載果如圖11-4d 所示。如果選用3 1替換3 0，而原來的3 1是樹葉節(jié)點(diǎn)，那么只需刪除該樹葉節(jié)點(diǎn)。
圖11-4 二叉搜索樹中元素的刪除
注意， 必須確保右子樹中的最小元素以及左子樹中的最大元素既不會(huì)在沒有子樹的節(jié)點(diǎn)中，
也不會(huì)在只有一個(gè)子樹的節(jié)點(diǎn)中?？梢园聪率龇椒▉聿檎业阶笞訕渲械淖畲笤兀菏紫纫苿?dòng)到
子樹的根，然后沿著各節(jié)點(diǎn)的右孩子指針移動(dòng)，直到右孩子指針為 0為止。類似地，也可以找
到右子樹中的最小元素：首先移動(dòng)到子樹的根，然后沿著各節(jié)點(diǎn)的左孩子指針移動(dòng)，直到左孩
子指針為0為止。
