二叉排序树的删除图解_二叉排序树的删除_二叉排序树的删除代码(4)

2.4二叉排序树中元素的删除

对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。

-2-

2.5 总体设计流程图

4.1程序总体流程图

-3-

3．详细设计

? Tnode的声明

typedef struct Tnode{

int data;

struct Tnode *lchild,*rchild;

}*node,BSTnode;

?

{

if(!t)

{*p=f;return (0);}

else

if(key==t->data) {*p=t;return (1);}

else

if(key<t->data) searchBST(t->lchild,key,t,p); else

searchBST(t->rchild,key,t,p);

}

?

{

node p=NULL,s=NULL;

if(!searchBST(*t,key,NULL,&p))

{

s=(node)malloc(sizeof(BSTnode));

s->data=key;

s->lchild=s->rchild=NULL;

if(!p) *t=s;

else

if(key<p->data) p->lchild=s;

else p->rchild=s;

-4-

searchBST的声明 searchBST(node t,int key,node f,node *p) insertBST的声明 insertBST(node *t,int key)

}

else

return (0);

}

?

{

if(*t){

if(inorderTraverse(&(*t)->lchild))printf("%d ",(*t)->data);

if(inorderTraverse(&(*t)->rchild));}

return(1) ;

}

?

{

node p=t,q=NULL,s,f;

while(p!=NULL)

{

if(p->data==key)

break;

q=p;

if(p->data>key) p=p->lchild;

else

p=p->rchild;

}

if(p==NULL)

return t;

if(p->lchild==NULL)

{

if(q==NULL) t=p->rchild;

else Delete类的声明 node Delete(node t,int key) inorderTraverse类的声明 inorderTraverse(node *t)

-5-

q->rchild=p->rchild;

free(p);

}

else{

f=p;

s=p->lchild;

while(s->rchild)

{

f=s;

s=s->rchild;

}

if(f==p) f->lchild=s->lchild;else f->rchild=s->lchild;p->data=s->data;

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