二叉排序樹上刪除結(jié)點(diǎn)算法的研究

黃淑芹,張 海

(安徽財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院, 安徽 蚌埠 233030)

1 二叉排序樹的相關(guān)概念

二叉排序樹是一種特殊的二叉樹，當(dāng)不允許有重復(fù)值時(shí)，二叉排序樹定義為：

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

可見，二叉排序樹是一種遞歸定義.當(dāng)中序遍歷二叉排序樹時(shí)可以得到一個(gè)遞增排序序列.

二叉排序樹的類型定義:

typedef struct BNode { // 結(jié)點(diǎn)結(jié)構(gòu)

KType key;

struct BNode *lchild, *rchild;

} BNode, *BTree;

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

2 借助遞歸和引用實(shí)現(xiàn)二叉排序樹上的刪除算法

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

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

則插入結(jié)點(diǎn)；

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

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

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 ); //繼續(xù)查找左子樹

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

}

} // Delete

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

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

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

}

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

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

}

else { // 左右子樹均不空

q = p; s = p->lchild;

while (s->rchild) { q = s; s = s->rchild; } // s 指向被刪結(jié)點(diǎn)的前驅(qū)

p->key = s->key;

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

else q->lchild = s->lchild;

delete s;

}

return TRUE;

} // Del

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

因?yàn)榻滩亩x了Search查找算法，在查找不成功時(shí)插入結(jié)點(diǎn).大家自然地認(rèn)為是當(dāng)查找成功時(shí)便刪除結(jié)點(diǎn)，同樣要調(diào)用查找算法.即：

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

則插入結(jié)點(diǎn)；

else

則刪除結(jié)點(diǎn)；

并且文獻(xiàn)[1]詳細(xì)地描述了被刪的結(jié)點(diǎn)與其雙親結(jié)點(diǎn)指針的變化，即：

(1)如果被刪的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則將其雙親結(jié)點(diǎn)中相應(yīng)指針設(shè)為“空”即可.

(2)如果被刪的結(jié)點(diǎn)只有左子樹或右子樹，則將其雙親結(jié)點(diǎn)的相應(yīng)指針設(shè)為指向被刪結(jié)點(diǎn)的左子樹或右子樹即可.

(3)如果被刪的結(jié)點(diǎn)既有左子樹又有右子樹，則用中序遍歷該樹時(shí)被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)替代它，再從樹中刪除前驅(qū)結(jié)點(diǎn).

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

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

為此修改文獻(xiàn)[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);} //繼續(xù)查找左子樹

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

}

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

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

Status Delete2(BTree &T, KType key)

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

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

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

else if(p==f2->lchild)

f2->lchild=p->lchild;

else f2->rchild=p->lchild;

free(p);}

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

{ if (p==T) //刪除結(jié)點(diǎn)為根結(jié)點(diǎn)

T=p->rchild;

else if(p==f2->lchild)

f2->lchild=p->rchild;

else f2->rchild=p->rchild;

free(p);}

else { //左右子樹都不空時(shí)

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 結(jié)束語

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

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].清華大學(xué)出版社,1997：227-231.

[2]譚浩強(qiáng).C++程序設(shè)計(jì)[M].清華大學(xué)出版社,2011：186-188.

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