二叉排序树.cpp

二叉排序树的查找算法

#include<stdio.h>
#include<stdlib.h>
typedef struct bitnode
{int data;
bitnode * lchild;
bitnode* rchild;
}bitnode,*bitree;

void insert(bitree &t,bitree s)
{bitree p,f;
	if (t==NULL)t=s;
else
{p=t;
while(p)
if(s->data<p->data)
{f=p;p=p->lchild;}
else
{f=p;p=p->rchild;}
if(s->data<f->data)
f->lchild=s;
else
f->rchild=s;
}
}

bitree createbst()
{bitree t,s;
int x;
t=NULL;
printf("输入节点9999 end \n");
scanf("%d",&x);
while(x!=9999)
{s=(bitree)malloc(sizeof(bitnode));
s->data=x;
s->lchild=s->rchild=NULL;
insert(t,s);
scanf("%d",&x);
}
return t;
}

void visit(bitree t)
{if(t==NULL) return ;
else
{visit(t->lchild);
printf("%d ",t->data);
visit(t->rchild);
}
}

bitree findnode(bitree t,int key)
{bitree p=t;
while(p)
if(p->data==key)
return p;
else if(p->data>key)
p=p->lchild;
else p=p->rchild;
return NULL;
}

void deletenode(bitree &t, int key)
{bitree p=t;
bitree q,s;
bitree f=NULL;
while(p!=NULL)
{if(p->data==key)

{ printf("%d \n",p->data); 
	
	if(!p->rchild)
	{if(p==t)
	   {t=t->lchild;
	     free(p);}
	else
	{q=p;
	if(f->rchild==p)
		f->rchild=p->lchild;
	else f->lchild=p->lchild;
	free(q);
	}
	}
	else if(!p->lchild)
	{if(p==t)
	{t=t->rchild;
	free(p);
	}
	else
	{q=p;
	if(f->lchild==p)
		f->lchild=p->rchild;
	else f->rchild=p->rchild;
     free(q);
	}
	}
	else
	{q=p;
	s=p->lchild;
	while(s->rchild)
	{q=s;s=s->rchild;}
	p->data=s->data;
	if(p!=q)
	q->rchild=s->lchild;
	else  q->lchild=s->lchild;
	}
break;}
else if(p->data>key)
{f=p;p=p->lchild;
}
else 
{f=p;p=p->rchild;}
}

if(p==NULL)
{printf("没有该节点\n");
return;}
}

void main()
{bitree t,p;
int key;
int m;
while(1)
{printf("1——建树且遍历；2——查找；3——删除节点0——退出\n");
scanf("%d",&m);
switch(m)
{	 case 1:  
	   t=createbst();
printf("对二叉树进行遍历的结果为：\n");
visit(t);
printf("\n");
break;
	 case 2:
printf("输入要查找的数字 \n");
scanf("%d",&key);
p=findnode(t,key);
if(p==NULL)
printf("该数不存在\n");
else printf("%d 已找到\n",p->data);
break;
	 case 3:
printf("输入要删除的节点\n");
scanf("%d",&key);
deletenode(t,key);
printf("删除节点后的结果为：\n");
visit(t);
printf("\n");
break;
}
if(m==0)break;
}
}