二叉排序树的查找_二叉排序树的查找效率_二叉排序树的查找方法(2)

else

{ if(kx>p->elem.key) p->rc=s; /*插入结点为p 的右子女*/

else p->lc=s; /*插入结点为p 的左子女*/

}

}

return flag;

}

四.二叉排序树删除操作

从二叉排序树中删除一个结点之后，使其仍能保持二叉排序树的特性即可。设待删结点为*p（p 为指向待删结点的指针），其双亲结点为*f，以下分三种情况进行讨论。

*p 结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针。如图9.6。

*p 结点只有右子树pr 或只有左子树pl，此时，只需将pr 或pl 替换*f 结点的*p 子树即可。如图9.7。

*p 结点既有左子树Pl 又有右子树Pr，可按中序遍历保持有序进行调整。

设删除*p 结点前，中序遍历序列为：

P 为F 的左子女时有：…，Pl 子树，P，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…

P 为F 的右子女时有：…，F，Pl 子树，P，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…

则删除*p 结点后，中序遍历序列应为：

P 为F 的左子女时有：…，Pl 子树，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…

P 为F 的右子女时有：…，F，Pl 子树，Pj ，S 子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…

有两种调整方法：

直接令pl 为*f 相应的子树，以pr 为pl 中序遍历的最后一个结点pk 的右子树；

令*p 结点的直接前驱Pr 或直接后继（对Pl子树中序遍历的最后一个结点Pk）替换*p 结点，再按⒉的方法删去Pr 或Pk。图9.8 所示的就是以*p 结点的直接前驱Pr 替换*p。二叉排序树的查找

【算法9.6】

int DeleteNode(NodeType **t,KeyType kx)

{ NodeType *p=*t,*q,*s,**f;

int flag=0;

if(SearchElem(*t,&p,&q,kx));

{ flag=1; /*查找成功，置删除成功标志*/

if(p= =q) f=&(*t); /*待删结点为根结点时*/

else /*待删结点非根结点时*/

{ f=&(p->lc); if(kx>p->elem.key) f=&(p->rc);

} /*f 指向待删结点的父结点的相应指针域*/

if(!q->rc) *f=q->lc; /*若待删结点无右子树，以左子树替换待删结点*/

else

{ if(!q->lc) *f=q->rc; /*若待删结点无左子树，以右子树替换待删结点*/

else /*既有左子树又有右子树*/

{ p=q->rc;s=p;

while(p->lc) {s=p;p=p->lc;}/*在右子树上搜索待删结点的前驱p*/

*f=p;p->lc=q->lc; /*替换待删结点q，重接左子树*/

if(s!=p)

{ s->lc=p->rc; /*待删结点的右子女有左子树时，还要重接右子树*/

p->rc=q->rc;

}

}

}

free(q);

}

return flag;

}

对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率同顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应对其调整，使其依然保持均匀。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25278-2.html