()二叉排序樹的刪除
從二叉排序樹中刪除一個結點不能把以該結點為根的子樹都刪去並且還要保證刪除後所得的二叉樹仍然滿足BST性質
①刪除操作的一般步驟
() 進行查找
查找時令p指向當前訪問到的結點parent指向其雙親(其初值為NULL)若樹中找不到被刪結點則返回否則被刪結點是*p
() 刪去*p
刪*p時應將*p的子樹(若有)仍連接在樹上且保持BST性質不變按*p的孩子數目分三種情況進行處理
②刪除*p結點的三種情況
()*p是葉子(即它的孩子數為)
無須連接*p的子樹只需將*p的雙親*parent中指向*p的指針域置空即可
()*p只有一個孩子*child
只需將*child和*p的雙親直接連接後即可刪去*p
注意
*p既可能是*parent的左孩子也可能是其右孩子而*child可能是*p的左孩子或右孩子故共有種狀態
()*p有兩個孩子
先令q=p將被刪結點的地址保存在q中;然後找*q的中序後繼*p並在查找過程中仍用parent記住*p的雙親位置*q的中序後繼
*p一定是*q的右子樹中最左下的結點它無左子樹因此可以將刪去*q的操作轉換為刪去的*p的操作即在釋放結點*p之前將其
數據復制到*q中就相當於刪去了*q具體【 參見動畫演示 】
③二叉排序樹刪除算法
分析
上述三種情況都能統一到情況()算法中只需針對情況()處理即可
注意邊界條件若parent為空被刪結點*p是根故刪去*p後應將child置為根
算法
void DelBSTNode(BSTree *TptrKeyType key)
{//在二叉排序樹*Tptr中刪去關鍵字為key的結點
BSTNode *parent=NUll*p=*Tptr*q*child;
while(p){ //從根開始查找關鍵字為key的待刪結點
if(p>key==key) break;//已找到跳出查找循環
parent=p; //parent指向*p的雙親
p=(keykey)?p>lchildp>rchild; //在關p的左或右子樹中繼續找
}
if(!p) return; //找不到被刪結點則返回
q=p; //q記住被刪結點*p
if(q>lchild&&q>rchild) //*q的兩個孩子均非空故找*q的中序後繼*p
for(parent=qp=q>rchild; p>lchild; parent=pp=p=>lchild);
//現在情況()已被轉換為情況()而情況()相當於是情況()中child=NULL的狀況
child=(p>lchild)?p>lchildp>rchild;//若是情況()則child非空;否則child為空
if(!parent) //*p的雙親為空說明*p為根刪*p後應修改根指針
*Tptr=child; //若是情況()則刪去*p後樹為空;否則child變為根
else{ //*p不是根將*p的孩子和*p的雙親進行連接*p從樹上被摘下
if(p==parent>lchild) //*p是雙親的左孩子
parent>lchild=child; //*child作為*parent的左孩子
else parent>rchild=child; //*child作為 parent的右孩子
if(p!=q) //是情況()需將*p的數據復制到*q
q>key=p>key; //若還有其它數據域亦需復制
} //endif
free(p); /釋放*p占用的空間
} //DelBSTNode
From:http://tw.wingwit.com/Article/program/sjjg/201311/23824.html
