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

else

if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/

else

searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/

}

insertBST(node *t,int key) /*插入函数*/

{

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;/*结点*s为新的根结点*/

else

if(key<p->data) p->lchild=s;/*结点*s为左孩子*/

else p->rchild=s; /*结点*s为右孩子*/

return (1);

}

else

-20-

return (0);/*}

inorderTraverse(node *t) /*中序遍历函数*/

{

if(*t){

if(inorderTraverse(&(*t)->lchild))/*中序遍历根的左子树*/printf("%d ",(*t)->data); /*输出根结点*/

if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/}

return(1) ;

}

node Delete(node t,int key) /*删除函数*/

{

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)/*p指向当前要删除的结点*/

{

if(q==NULL) t=p->rchild; /*q指向要删结点的父母*/

else

if(q->lchild==p) q->lchild=p->rchild; /*p为q的左孩子*/

else

q->rchild=p->rchild;/*p为q的右孩子*/

free(p);

}

else{/*p的左孩子不为空*/

f=p;

s=p->lchild;

while(s->rchild) /*左拐后向右走到底*/

{

f=s;

s=s->rchild;

}

if(f==p) f->lchild=s->lchild; /*重接f的左子树*/

-21-

elsep->data=s->data;

free (s);

}

return t;

}

void main()

{

node T=NULL;

int num;

int s=0,j=0,i=0;

int ch=0;

node p=NULL;

printf("输入一串数，每个数以空格分开:");

do{

scanf("%d",&num);

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