二叉排序樹上刪除結點算法的研究

黃淑芹,張 海

(安徽財經大學 管理科學與工程學院, 安徽 蚌埠 233030)

1 二叉排序樹的相關概念

二叉排序樹是一種特殊的二叉樹，當不允許有重復值時，二叉排序樹定義為：

二叉排序樹可以是一棵空樹；或者是滿足如下特性的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；它的左、右子樹也都分別是二叉排序樹.

可見，二叉排序樹是一種遞歸定義.當中序遍歷二叉排序樹時可以得到一個遞增排序序列.

二叉排序樹的類型定義:

typedef struct BNode { // 結點結構

KType key;

struct BNode *lchild, *rchild;

} BNode, *BTree;

查找、插入和刪除是二叉排序樹的重要操作.為了更好地分析刪除操作和查找操作的關系，引入另一種刪除操作思路，為了與文獻[1]刪除操作的實現思路更好地比較.下面首先分析文獻[1]的刪除思路.

2 借助遞歸和引用實現二叉排序樹上的刪除算法

在文獻[1]中，詳細描述了查找算法Search和插入算法Insert，并且處理插入操作時是基于查找算法Search實現的.即如果查找不成功則插入.

If (!Search(T,key,NULL,p) )

則插入結點；

但文獻[1]在處理刪除操作時，沒有調用Search查找算法，而是巧妙地借助C++中的引用，單獨建立了一個刪除算法，在該算法中實現查找，查找成功則刪除，也就是邊查找邊刪除.

刪除結點和其雙親結點的關系是通過遞歸和引用[2]實現的.通過Delete(T->lchild,key)、 Delete(T->rchild,key)遞歸調用算法Delete(T,key)時，因為T->lchild和T->rchild一定是T的孩子，并且借助于Del(&p)算法中的引用把“父子關系”帶到遞歸的下一層.為了便于比較，其刪除算法如下：

Status Delete (BTree &T, KType key ) {

if (!T) return FALSE; // 不存在key元素

else { if (key==T->key) //存在key元素

return Del(T);

else if (keykey)

return Delete ( T->lchild, key ); //繼續查找左子樹

else return Delete ( T->rchild, key ); // 繼續查找右子樹

}

} // Delete

void Del ( BTree &p ){ //借助于引用，T向下層遞進

if (!p->rchild) { // 右子樹為空樹時

q = p; p = p->lchild; free(q);

}

else if (!p->lchild) { // 左子樹為空樹時

q = p; p = p->rchild; free(q);

}

else { // 左右子樹均不空

q = p; s = p->lchild;

while (s->rchild) { q = s; s = s->rchild; } // s 指向被刪結點的前驅

p->key = s->key;

if (q != p ) q->rchild = s->lchild;

else q->lchild = s->lchild;

delete s;

}

return TRUE;

} // Del

3 基于Search查找算法的刪除算法

因為教材定義了Search查找算法，在查找不成功時插入結點.大家自然地認為是當查找成功時便刪除結點，同樣要調用查找算法.即：

if (!Search(T,key,NULL,p))

則插入結點；

else

則刪除結點；

并且文獻[1]詳細地描述了被刪的結點與其雙親結點指針的變化，即：

(1)如果被刪的結點為葉子結點，則將其雙親結點中相應指針設為“空”即可.

(2)如果被刪的結點只有左子樹或右子樹，則將其雙親結點的相應指針設為指向被刪結點的左子樹或右子樹即可.

(3)如果被刪的結點既有左子樹又有右子樹，則用中序遍歷該樹時被刪結點的前驅結點替代它，再從樹中刪除前驅結點.

而在實際刪除算法中卻用了遞歸和引用實現刪除結點時雙親指針的變化，沒有顯式地體現刪除結點時雙親指針的變化，這就給很多讀者帶來了疑惑，甚至有的讀者沒有讀懂文獻[1]的刪除算法，認為刪除結點時沒有正確地修改雙親結點的指針，是錯誤的[3].

為了便于大家更好地理解二叉排序樹上的刪除操作，和二叉排序樹上的插入操作思路保持一致(插入算法Insert中調用了查找算法Search，在刪除算法中也調用查找Search算法)，這里提出了刪除操作的另一種算法，在實現該算法前，要先修改查找算法Search.因為在文獻[1]的查找算法Search中，指針f指向T的雙親，由于在算法內沒有像給p賦值(如p=f或p=T)一樣給f單獨賦值，f值是不能帶給其他函數的，且f所指并不是p的雙親.為了查找成功實現刪除時，正確地修改雙親結點的指針，必須能使p的雙親保存下來，并能帶回刪除算法.

為此修改文獻[1]的查找算法Search為Search2，算法如下：

Status Search2(BTree T, KType key,BTree f, BTree &p,BTree &f2 ) {

if (!T)

{ p=f; return FALSE; } // 沒找到key元素

else if ( key==T->key)

{ p = T; f2=f; return TRUE; } // 找到key元素

else if ( keykey)

{return Search(T->lchild, key, T, p,f2);} //繼續查找左子樹

else {return Search(T->rchild, key, T, p,f2);} //繼續查找右子樹

}

在查找算法Search2中，增設了一個指向*p的雙親*f2參數，當查找成功f2始終指向*p的雙親結點，并使用引用將其值帶入刪除算法，當p指向根節點時，f2為NULL.算法中語句f2=f是必須的，否則后面的刪除算法Delete2中的f2不能正常使用.

基于查找算法Search2的刪除算法修改如下：

Status Delete2(BTree &T, KType key)

{ if(Search2(T,key,f,p,f2))

{if (!p->rchild) //右子樹為空樹時

{ if (p==T) T=p->lchild;//刪除的結點為根節點

else if(p==f2->lchild)

f2->lchild=p->lchild;

else f2->rchild=p->lchild;

free(p);}

else if (!p->lchild) //左子樹為空樹時

{ if (p==T) //刪除結點為根結點

T=p->rchild;

else if(p==f2->lchild)

f2->lchild=p->rchild;

else f2->rchild=p->rchild;

free(p);}

else { //左右子樹都不空時

q = p; s = p->lchild;

while (s->rchild) { q = s; s = s->rchild; }

p->key = s->key;

if(q!=p)q->rchild=s->lchild;

else q->lchild = s->lchild;

free(s);}

return TRUE;

}

return FALSE;

}

4 結束語

本文就文獻[1]在二叉排序樹上的刪除操作給予了詳細地分析和比較，并提出了基于查找算法的刪除算法，一方面旨在幫助大家理解遞歸和引用在算法中的巧妙應用，另一方面和插入算法的思路保持了統一性，使大家更好地理解刪除算法.希望本文對同仁的數據結構課程教學有所幫助.

參考文獻：

[1]嚴蔚敏，吳偉民.數據結構(C語言版)[M].清華大學出版社,1997：227-231.

[2]譚浩強.C++程序設計[M].清華大學出版社,2011：186-188.

[3]陳建國. 在二叉排序樹上刪除一個結點的算法改進[J].太原科技,2001(1):27-28.