二叉排序树.c

数据结构的二杈树查找

#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef int KEYTYPE;
//-------二叉排序树的二叉链表存储表示-----
typedef struct node{
	KEYTYPE key;
	struct node *lchild,*rchild;
}BSTNODE;

BSTNODE*  searchnode(int w,BSTNODE *r)
{   //按给定值在二叉排序树中查询
	BSTNODE *p;
	if(r==NULL)p=NULL;//空二叉排序树
	else
	{
		if(w==r->key)p=r;//给定值和根结点相同
		else if(w>r->key) p=searchnode(w,r->rchild);//递归继续查询
		else p=searchnode(w,r->lchild);
	}
	return p;
}

BSTNODE*  insert_bst(int w,BSTNODE *p)
{   //将一个元素插入二叉排序树中
	if(p==NULL)//如果二叉排序树空，p作为新二叉排序树中的根结点
	{
		p=malloc(sizeof(BSTNODE));
		p->lchild=NULL;p->rchild=NULL;p->key=w;
	}
	//如果二叉排序树不空，p作为叶子结点递归插入二叉排序树中
	else if(w>p->key) p->rchild=insert_bst(w,p->rchild);
	     else p->lchild=insert_bst(w,p->lchild);
	return p;//返回根结点
}

BSTNODE*  getfather(BSTNODE *p,BSTNODE *r)
{   //在以r为根的二叉排序树中查询p结点的双亲结点并返回双亲结点的地址
	BSTNODE *pf;
	if(r==NULL||p==r) pf=NULL;
	else
	{
		if(p==r->lchild||p==r->rchild) pf=r;
	    else if(p->key>r->key) pf=getfather(p,r->rchild);
		else pf=getfather(p,r->lchild);
	}
	return pf;
}

BSTNODE*  dele_bst(BSTNODE *p,BSTNODE *r)
{   //p结点存在，在以r为根的二叉排序树中删除p结点
	BSTNODE *temp,*tfather,*pf;
	//查找p结点的双亲结点，返回双亲结点的地址pf
	pf=getfather(p,r);
	if(p->lchild==NULL&&p->rchild==NULL&&pf!=NULL)
	//被删除结点是叶子结点，不是根结点
		if(pf->lchild==p) pf->lchild=NULL;
			else pf->rchild=NULL;
	if(p->lchild==NULL&&p->rchild==NULL&&pf==NULL) r=NULL;
	//被删除结点是叶子结点，又是根结点
	if(p->lchild==NULL&&p->rchild!=NULL&&pf!=NULL)
	//被删除结点有右孩子，无左孩子，不是根结点
		if(pf->lchild==p) pf->lchild=p->rchild;
			else pf->rchild=p->rchild;
	if(p->lchild==NULL&&p->rchild!=NULL&&pf==NULL) r=p->rchild;
	//被删除结点有右孩子，无左孩子，又是根结点
	if(p->lchild!=NULL&&p->rchild==NULL&&pf!=NULL) 
	//被删除结点有左孩子，无右孩子，不是根结点
		if(pf->lchild==p) pf->lchild=p->lchild;
			else pf->rchild=p->lchild;
	if(p->lchild!=NULL&&p->rchild==NULL&&pf==NULL) r=p->lchild;
	//被删除结点有左孩子，无右孩子，又是根结点
	if(p->lchild!=NULL&&p->rchild!=NULL)
	//被删除结点有左孩子，又有右孩子
	{
		temp=p->lchild;tfather=p;
		while(temp->rchild!=NULL)
		{
			tfather=temp;
			temp=temp->rchild;
		}
		p->key=temp->key;
		if(tfather!=p) tfather->rchild=temp->lchild;
		else tfather->lchild=temp->lchild;
	}
	printf("\n");
	if(r!=NULL) printf("二叉排序树的根是%d\n\n",r->key);
	else printf("二叉排序树空\n\n");
    return r; 
}

void print_bst(BSTNODE *p)
{   //显示二叉排序树
	if(p!=NULL)
	{
		print_bst(p->lchild);
		printf("%d  ",p->key);
		if(p->lchild!=NULL) printf("%d的左结点是%d  ",p->key,p->lchild->key);
		else printf("%d无左结点  ",p->key);
		if(p->rchild!=NULL) printf("%d的右结点是%d  ",p->key,p->rchild->key);
		else printf("%d无右结点  ",p->key);
		printf("\n");
		print_bst(p->rchild);
	}
}

BSTNODE*  create_bst()
{   //建立二叉排序树
	BSTNODE *p,*root;
	int loop=0;
	int s;
	root=NULL;
	do
	{
		printf("\n");
		printf("输入结点数据（整数，结束输入0）：");
	    scanf("%d",&s);
		if(s==0) loop=1;
		else
		{
			p=searchnode(s,root);
			if(p==NULL)//输入的数据不在二叉排序树中，方可插入二叉排序树
			{
				root=insert_bst(s,root);
				print_bst(root);//边插入边显示二叉排序树中结点值
			}
			else
				printf("输入的数据已存在，不能插入!!\n");
		}
		if(root!=NULL) printf("\n二叉排序树根结点为:%d\n\n",root->key);
	}while(!loop);
	return root;
}

BSTNODE *insert(BSTNODE* root)
{   //将用户输入的结点插入二叉排序树中
	int s;
	BSTNODE *p;
	printf("\n");
    printf("输入要插入的结点数据（整数，结束请输入0）：");
	scanf("%d",&s);
	if(s!=0)
	{
		p=searchnode(s,root);
		if(p==NULL)//输入的数据不在二叉排序树中，方可插入二叉排序树
		{
			root=insert_bst(s,root);
			print_bst(root);//边插入边显示二叉排序树中结点值
		}
		else
			printf("结点已存在，不能插入!!\n");
	}	
	return root;
}

void search_bst(BSTNODE* root)
{   //在二叉排序树中查询用户输入的结点是否存在
	int s;
	BSTNODE *p;
	printf("\n");
    printf("输入待查结点值（整数）：");
	scanf("%d",&s);
	if(s!=0)
	{
		p=searchnode(s,root);
		if(p==NULL) printf("结点不存在!\n");
		else printf("结点存在!!\n");
	}	
}

BSTNODE*  deleted(BSTNODE* root)
{   ////在二叉排序树中删除用户指定的结点
	int s;
	BSTNODE *p;
	char ch;
	printf("\n");
    printf("输入待删除结点值（整数）：");
	scanf("%d",&s);
	if(s!=0)
	{
		p=searchnode(s,root);//用户指定要删除的结点存在吗？
		if(p==NULL) printf("结点不存在!\n\n");//结点不存在
		else
		{
			printf("结点存在,删除吗?(Y/N)");
			fflush(stdin);
			scanf("%c",&ch);
			if((ch=='y')||(ch=='Y'))//结点存在，确认删除
			{
				root=dele_bst(p,root);print_bst(root);
			}
		}	
	}
	return root;
}

main()
{
  BSTNODE *root;
  int loop,i;
  loop=1;
  while(loop)
  {
	  printf("\n\n\n");
	  printf("       1:二叉排序树--建立\n");
	  printf("       2:二叉排序树--插入\n");
	  printf("       3:二叉排序树--查找\n");
	  printf("       4:二叉排序树--删除\n");
	  printf("       5:二叉排序树--显示\n");
	  printf("       0:退出\n");
      scanf("%d",&i);
	  switch(i)
	  {
	    case 0:loop=0;break;//退出
	    case 1:root=create_bst();break;//建立
	    case 2:root=insert(root);break;//插入
		case 3:search_bst(root);break;//查找
		case 4:root=deleted(root);break;//删除
		case 5:printf("\n");//显示
			if(root!=NULL) printf("二叉排序树的根是%d\n",root->key);
			print_bst(root);break;
	  }
  }
}