二叉排序树C语言.doc

二叉排序树
#include <stdio.h>
#include<malloc.h>
typedef struct node
{int data;
struct node *lchild,*rchild;
} bitree;
/*插入操作函数*/
bitree *insertbitree(bitree *p,int b)
{
if(p==NULL)
{
p=(bitree *)malloc(sizeof(bitree));
p->data=b;
p->lchild=NULL;
p->rchild=NULL;
}
else if(b<p->data)
p->lchild=insertbitree(p->lchild,b);
else p->rchild=insertbitree(p->rchild,b);
return(p);
}

/*建立二叉排序树函数*/
bitree *creatbitree(bitree *t)
{
int key;
t=NULL;
printf("输入二叉排序树的数值（以输入0结束）：");
scanf("%d",&key);
while(key!=0)
{
t=insertbitree(t,key);
scanf("%d",&key);
}
return(t);
}

/*删除二叉排序树上的结点函数*/
bitree *del(bitree *t)
{
int fag,k;
bitree *p,*s,*q,*f;
p=t;f=NULL;
printf("输入要删除的结点值:");
scanf("%d",&k);
while(p!=NULL) /*查找关键字为K的待删除结点*/
{
if(p->data==k) break; /*找到，跳出查找循环*/
f=p;
if(p->data>k) p=p->lchild;
else p=p->rchild;
}
if(p==NULL) printf("要删除的结点不在此二叉排序树中。");
if(p->lchild==NULL) /* *p无左子树*/
{
if(f==NULL) t=p->rchild;
else if(f->lchild==p)
f->lchild=p->rchild;
else
f->rchild=p->rchild;
free(p);
}
else /* *p有左子树*/
{
q=p;
s=p->lchild;
while(s->rchild!=NULL)
{
q=s;
s=s->rchild;
}
if(q==p)
q->lchild=s->lchild;
else
q->rchild=s->lchild;
p->data=s->data;
free(s);
fag=1;
}
return(t);
}
/*中序遍历在屏幕上输出二叉排序树函数*/
void inorder(bitree *t)
{ if(t)
{
inorder(t->lchild);
printf(" %d ",t->data);
inorder(t->rchild);
}
}
void main()
{
bitree *root;
int t;
root=creatbitree(root);
printf("\n根节点是：%d\n",root->data);
printf("建立的二叉树中的节点是：\n");
inorder(root);
printf("\n是否进行删除操作[1=是，2=否]:");
scanf("%d",&t);
if(t==1)
{
root=del(root);
printf("\n进行删除操作后的数据:");
inorder(root);
}
else if(t==2)
printf("\n不进行删除操作.");
}