二叉排序树上删除结点算法的研究

黄淑芹,张 海

(安徽财经大学 管理科学与工程学院, 安徽 蚌埠 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.