二叉排序树.c

无需密码,直接解压,是老师布置的二叉排序树的C语言代码,适合学生使用.

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define maxsize 20
typedef struct BSnode
{
	int data;
	struct BSnode *lchild,*rchild;
}BST,*BSP;
BSP creat(int key)             /*创建一个结点*/
{
	BSP s;
	s=(BSP)malloc(sizeof(BST));
	s->data=key;
	s->lchild=s->rchild=NULL;
	return s;
}
BSP insert(BSP t,BSP s)          /*将s指向的数据插入到t指向的二叉树中*/
{
	BSP q,p;
	if(t==NULL)
		return s;
	p=t;
	q=NULL;
	while(p)
	{
		q=p;
		if(s->data==p->data)
		{
			printf("该结点%d已经存在!\n",s->data);
			return t;
		}
		if(s->data<p->data)
			p=p->lchild;
		else
			p=p->rchild;
	}   
	if(s->data<q->data)
		q->lchild=s;
	else 
		q->rchild=s;
	return t;
}
void intravel(BSP t)          /*中根遍历*/
{
	if(t)
	{
		intravel(t->lchild);
        printf("%d ",t->data);
		intravel(t->rchild);
	}
}
void pretravel(BSP t)          /*先根遍历*/
{
	if(t)
	{
		printf("%d ",t->data);
		pretravel(t->lchild);
        pretravel(t->rchild);
	}
}
void lasttravel(BSP t)          /*后根遍历*/
{
	if(t)
	{
        lasttravel(t->lchild);
        lasttravel(t->rchild);
		printf("%d ",t->data);
	}
}
void leveltravel(BSP t)
{
	BSP queue[maxsize],p;  /*定义队列所使用的数组空间,元素类型为指向节点的指针类型*/
	int front=0,rear=0;  /*定义队首和队尾指针,初始均置0表示空队*/
	p=t;
	if(p!=NULL)     /*将树根指针进队*/
	{
		rear=(rear+1)%maxsize;
		queue[rear]=p;
	}
	while(front!=rear)  /*队列不空时循环*/
	{
		front=(front+1)%maxsize;   /*使队首指针指向队首元素*/
		p=queue[front];            /*删除队首无素*/
		printf("%d ",p->data);     /*输出队首无素所指节点的值*/
		if(p->lchild!=NULL)        /*若节点存在左孩子,则左子点指针进队*/
		{
			rear=(rear+1)%maxsize;
			queue[rear]=p->lchild;
		}
		if(p->rchild!=NULL)         /*若节点存在右孩子,则右子点指针进队*/
		{
			rear=(rear+1)%maxsize;
			queue[rear]=p->rchild;
		}
	}
}

struct stack
{                              /*定义临时堆栈*/
	int top;                   /*栈顶指针*/
	BSP num[maxsize];          /*指针数组*/
};
void intravelstack(BSP t)      /*中根遍历非递归算法*/
{
	struct stack p;
	BSP q;
	q=t;                     /*q为指向树根结点*/
	p.top=-1;                /*栈顶指针初始化*/
	do
	{
		while(q!=NULL)       /*如果二叉树不为空则开始遍历*/
		{
			if(p.top<maxsize) /*将指向树根结点的指针入栈*/
			{
				p.top++;
				p.num[p.top]=q;
				q=q->lchild;
			}
			else
				printf("堆栈已满!\n");
		}
		if(p.top>-1)         /*从栈顶弹出上一次访问过的结点的指针*/
		{
			q=p.num[p.top];
			p.top--;
			printf("%d ",q->data);
			q=q->rchild;
		}
	}while((p.top!=-1)||(q!=NULL));
}
		

BSP delet(BSP t,int k)       /*删除数据k*/
{
	BSP q,p,f,h;
	p=t;q=NULL;
	while(p)
	{
		if(p->data==k)
			break;
		q=p;
		if(k<p->data)
			p=p->lchild;
		else
			p=p->rchild;
	}
	if(p==NULL)
	{
		printf("该数值在二叉树中不存在!\n");
		return t;
	}
	if(p->lchild==NULL)
	{
		if(q==NULL)
			t=p->rchild;
		else if(q->lchild==p)
			q->lchild=p->rchild;
		else
			q->rchild=p->rchild;
		free(p);
	}
	else
	{
		f=p;h=p->lchild;
		while(h->rchild)
		{
			f=h;
			h=h->rchild;
			p->data=h->data;
		}
			if(f!=p)
				f->rchild=h->lchild;
			else
				f->lchild=h->lchild;
			free(h);
	}
	return t;
}
int treehigh(BSP t)
{
	int lh,rh,h;
	if(t==NULL)
		h=0;
	else
	{
		lh=treehigh(t->lchild);     /*求左子树的深度*/
		rh=treehigh(t->rchild);     /*求右子树的深度*/
		h=(lh>=rh?lh:rh)+1;          /*二叉树的深度为左右子树中深度较大者加1*/
	}
	return h;         /*返回二叉树的深度值*/
}
int leaf(BSP t)    /*统计叶子结点的个数*/
{
	int static leaves=0;
	if(t)
	{
		leaf(t->lchild);       /*统计左子树内的叶子结点个数*/
		if(!(t->lchild||t->rchild))
			leaves++;
		leaf(t->rchild);       /*统计右子树内的叶子结点个数*/
	}
	return leaves;
}
BSP find(BSP t,int i)
{
	int flag=0;
	BSP p;
	p=t;
	while((p!=NULL)&&(flag==0))
	{
		if(i==p->data)
		   flag=1;
	    else if(i<p->data)
		   p=p->lchild;
        else p=p->rchild;
	}
    return p;
}
void changetree(BSP *t)       /*交换二驻树左右子树的算法*/
{
	BSP temp;
	if(*t)                    /*t是指向中二叉树根结点的指针*/
	{
		changetree(&(*t)->lchild);   /*将左子树内的结点左右交换*/
		changetree(&(*t)->rchild);   /*将右子树内的结点左右交换*/
		temp=(*t)->lchild;       /*将根结点左右指针的指向进行交换*/
		(*t)->lchild=(*t)->rchild;
		(*t)->rchild=temp;
	}
}

void menu()
{printf("\t\t            ***欢迎使用二叉树系统!***\n");
 printf("\t\t **************************************************\n");
 printf("\t\t|         1.建立二叉树　　　　　　　　             |\n");
 printf("\t\t|         2.插入数据　　　　　　                   |\n");
 printf("\t\t|         3.删除数据　　　　　　　　          　   |\n");
 printf("\t\t|         4.遍历二叉树                             |\n");
 printf("\t\t|         5.在二叉树中查找给定关键字               |\n");
 printf("\t\t|         6.交换各结点的左右子树                   |\n");
 printf("\t\t|         7.二叉树的深度、叶子结点数               |\n");
 printf("\t\t|         8.退出系统                               |\n");
 printf("\t\t **************************************************\n");
}
void menu2()
{printf("\t\t               ***遍历二叉树的方法!***\n");
 printf("\t\t **************************************************\n");
 printf("\t\t|         1.先根遍历　　　　　　　　               |\n");
 printf("\t\t|         2.中根遍历　　　　　　                   |\n");
 printf("\t\t|         3.后根遍历　　　　　　　　          　   |\n");
 printf("\t\t|         4.层次遍历                               |\n");
 printf("\t\t|         5.中根遍历非递归遍历                     |\n");
 printf("\t\t|         6.退出                                   |\n");
 printf("\t\t **************************************************\n");
}
void travel(BSP t)        /*实现各种遍历的选择*/
{
	int i;
    menu2();
    star:printf("请输入你的选择:\n");
	scanf("%d",&i);
	switch(i)
	{
	case 1:
		{
			pretravel(t);
            printf("\nplease press enter to continue!\n");
			getch();
			goto star;
		}
	case 2:
		{
			intravel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			goto star;
		}
	case 3:
		{
			lasttravel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			goto star;
		}
	case 4:
		{
			leveltravel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			goto star;
		}
	case 5:
		{
			intravelstack(t);
			printf("\nplease press enter to continue!\n");
			getch();
			goto star;
		}
	case 6:break;
	}
}
main()
{
	BSP t,s,p;
	int key,n,i;
	char ch;
star:menu();
	printf("请输入你的选择:\n");
	scanf("%d",&n);
	switch(n)
	{
	case 1:
		{
			printf("请输入数据:\n");
	        scanf("%d",&key);
	        t=creat(key);
	        scanf("%d",&key);
	        while(key!=0)
			{
		        s=creat(key);
		        t=insert(t,s);
		        scanf("%d",&key);
			}
			intravel(t);
            printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 2:
		{
			printf("请输入要插入的数据:\n");
		    scanf("%d",&key);
			s=creat(key);
			t=insert(t,s);
			intravel(t);
            printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 3:
		{
			printf("请输入要删除的数据:\n");
			scanf("%d",&key);
			delet(t,key);
			intravel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 4:
		{
			travel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 5:
		{
            printf("请输入要查找的数据:\n");
			scanf("%d",&i);
			p=find(t,i);
			if(p)
				printf("%d在二叉树中存在,地址为%d!\n",i,p);
			else printf("%d在二叉树中不存在!\n",i);
			printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 6:
		{
			changetree(&t);
            intravel(t);
			printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
	case 7:
		{
			i=treehigh(t);
			printf("该树的深度为%d\n",i);
			i=leaf(t);
			printf("该树的叶子结点数为%d\n",i);
			printf("\nplease press enter to continue!\n");
			getch();
			system("cls");
			goto star;
		}
    case 8:
		{
		    printf("是否退出系统?(y/n)\n");
		    getchar();
			ch=getchar();
		    if(ch=='y'||ch=='Y')
		        exit(0); 
		    else
			{
			    printf("press the enter to continue!\n");
			    getch();
		        system("cls");
			    goto star;
			}
		}
	}
	
}