源程序.txt.txt

排序二叉树的应用数据结构课程设计.自己用来交过学期的设计报告.用好了请评价.

#include <conio.h>
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <string.h>

typedef struct treenode *treeptr;  //重定义机构指针类型为treeptrstruct treenode  //树结点的基本数据结构
{
	int key;  //数据域
	char data[20];  //数据域
	treeptr left,right;  //左,右指针
};
//主要的树函数的说明部分
void prttree(treeptr tnode,int t);
treeptr instree(char *s,int key,treeptr tnode);
treeptr membertree(char *s,treeptr tnode);
treeptr deltree(char *s,treeptr tnode);
treeptr findinspos(char *s,treeptr tnode);

main( )
{
	treeptr tp,t;
	char ch;
	char s[80];
	int key;
	int i;
	tp=NULL;  //初始化根结点指针
	while(1)
	{	
		clrscr();
		gotoxy(20,5);
		printf("I-Insert an element into the tree");
		gotoxy(20,6);
		printf("D-Delete an element from the tree");
		gotoxy(20,7);
		printf("F-Find a member in the tree");
		gotoxy(20,8);
		printf("P-Print the tree");
		gotoxy(20,9);
		printf("Q-Quit");
		gotoxy(20,12);
		print("Make a seletion > > >");
		ch=getche();
		ch=toupper(ch);
		switch(ch)
		{	
			case 'I':
				printf("\nEnter element name > > >");  //插入一个元素
				scanf("%s",s);	
				printf("\nEnter element key (a number) > > >");
				scanf("%d",&key);
				if((tp=instree(s,key,tp))!=NULL)
					printf("\nElement inserted,press any key to continue");
				else
					printf("\nElement can't be inserted,press any key to continue");
				getch();
				break;
			case 'D':
				printf("\nEnter element > > >");  //删除一个元素
				scanf("%s",s);
				tp=deltree(s,tp);
				break;
			case 'F':
				printf("\nEnter element > > >");  //查找一个元素
				scanf("%s",s);
				t=membertree(s,tp);
				if(t!=NULL)
				{
					printf("\n The Element is %s %d",t->data,t->key);
				}
				else
					printf("\nElement not found");
				getch();
				break;
			case 'P':  //打印树
				gotoxy(20,14);
				printf("0--Prinf preorder");
				gotoxy(20,15);
				printf("1--Prinf inorder");	
				gotoxy(20,16);
				printf("2--Prinf postorder");
				gotoxy(20,18);
				printf("Enter option > > >");
				scanf("%d",&i);
				printf("\n");
				prttree(tp,i);
				getch();
				break;
			case 'Q':
				exit(0);  //退出
			default:
				printf("\nInvalid selection");
			}
		}
	}


//主要树函数
void prttree(treeptr tnode,int t)
//该函数在屏幕上打印出存放在树中的元素,如果是空树,则无输出.
//参数：
	tnode-指向根结点的指针;*/
	t-打印方式:
		0:先序
		1:中序
  		2:后序
{
	if(tnode!=NULL)  //打印成员
	{	
		switch(t)
		{
			case 0:
				printf("\n%s :%d",tnode->data,tnode->key);
				prttree(tnode->left,t);
				prttree(tnode->right,t);
				break;
			case 1:
				prttree(tnode->left,t);
				printf("\n%s:%d",tnode->data,tnode->key);
				prttree(tnode->right,t);
				break;
			case 2:
				prttree(tonde->left,t);
				prttree(tonde->right,t);
				printf("\n%s:%d",tnode->data,tnode->key);
				break;
			default:
				printf("\nInvalid printf selection");
		}
	}
}

treeptr instree(char *s,int key,treeptr tnode)
//该参数把一个元素插入到二叉树中.
//参数：
	s,key-接收插入数据;
	tnode-是指向根结点的指针
{
	treeptr t1,t2;
	t1=(treeptr)malloc(sizeof(struct treenode));  //分配空间
	if(t1==NULL)
	{
		printf("Memory is full\n");
		printf("Insert is failure\n");
		return(tnode);
	}
	else
	{
		t1->right=NULL;
		t1->left=NULL;
		t1->key=key;
		strcpy(t1->data,s);
		if(tnode==NULL)
			return(t1);
		else
		{
			t2=findinspos(s,tnode);  //得到要插入的位置
			if((strcmp(t2->data,s))<=0)
				t2->right=t1;  //插入右孩子
			else
				t2->left=t1;  //插入左孩子
			return(tnode);
		};  //插入完毕
	}
}

treeptr membertree(char *s,treeptr tnode)
//该函数测定树中的指定元素,如果元素是树中的成员,则函树返回该元素,否则返回NULL指针
//参数：
	s-指向要找的那个串的指针;
	tnode-指向树根结点的指针.
{
	treeptr t;
	int cmp;
	t=tnode;
	while(t!=NULL)
	{
		cmp=strcmp(t->data,s);
		if(cmp==0)
			return(t);  //找到元素
		else  if(cmp<0)
			t=t->right;  //查找右子树
		      else
			t=t->left;  //查找左子树
	}
	return(NULL);
}

treeptr  deltree(char *s,treeptr tnode)
//该函数删除一个结点
//参数：
	s-要删除的结点的数据域的值;
	tnode-指向根结点的指针.
{
	treeptr t1,t2;
	int ch;
	if(tnode==NULL)
		return(NULL);  //元素不能删除
	ch=strcmp(tnode->data,s);  //比较元素
	if(ch==0)  //找到元素
	{
		if((tnode->right==NULL)&&(tnode->left==NULL))
		{   	    //结点就是要删除的结点
			free(tnode->data);
			free(tnode);
			return(NULL);
		}
		else   	if(tnode->left==NULL)
			{	    //删除只带右孩子的根结点
				t1=tnode->right;  //使右孩子成为一棵新树根
				free(tnode->data);
				free(tnode);
				return(t1);
			}
			else  	if(tnode->right==NULL)
				{		//删除只带左孩子的根结点
					t1=tnode->left;  //使左孩子成为一棵新的根
					free(tnode->data);
					free(tnode);
					return(t1);
				}
				else  //删除带左,右孩子的根结点
				{
					t1=tnode->right;  //使右结点成为新根
					t2=tnode->right;
					while(t2->left!=NULL)  //查找新根左边所有的结点
						t2=t2->left;
					t2->left=tnode->left;  //连结老根的左结点
					free(tnode->data);
					free(tnode);
					return(t1);
				}
	}
	else	if(ch>0)
			tnode->left=deltree(s,tnode->left);
		else
			tnode->right=deltree(s,tnode->right);
	return(tnode);
}

treeptr findinspos(char *s,treeptr tnode)
//该函数寻找一个元素要插入的位置
{
	if((strcmp(tnode->data,s))>=0)
	{
		if(tnode->left==NULL)
			return(tnode);
		else
			findinspos(s,tnode->left);
	}
	else
	{
		if(tnode->right==NULL)
			return(tnode);
		else
			findinspos(s,tnode->right);
	}
}