二叉树.txt

二叉数

                                    free(tnode->data)
                                        
                                                                   
                                         free(tnode)


              return(t1)




                               结  束





五、源程序
程序清单：
#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);
	}
}
		


六 、参考资料
1 、赵逢禹、罗道昆、路玲、杜光耀 .  数据结构与C语言高级程序设计 .  北京航空航天大学出版社
2 、严蔚敏、吴伟民 .  数据结构(C语言版)  .  清华大学出版社
3 、严蔚敏、吴伟民、米宁 .  数据结构题集(C语言版)  .  清华大学出版社
七 、用户手册
本程序在VC++环境下运行
八 、运行结果
      A:\11.exe
 九、课程总结
短短二周的课程设计时间很快就过去了，而我所选的“二叉树的应用”设计题目也接近尾声。这期间，有老师的指导，有同学的帮助，有自己不懂就翻阅资料寻求解答的努力。经过磕磕碰碰总算完了任务。虽然所做的程序算不上了自己最满意的，但却是这二个星期以来的努力成果，是这学期学数据结构的总结，是对自己能力的考验，是自己尽最大努力做出来的。
在课程设计的过程当中，是对平时学习的检测，虽然平时书上所讲似乎懂了，就如我所做的“二叉树的应该”一样，但在真正设计起程序来，很多困难还是意想不到的，那只能在设计过程中不断的摸索，在摸索中不断提升自己。
二周课程设计的时间是过去了，但是，对数据结构的学习似乎才是开始，以后要学习的还很多很多，前面要走的路还很远很远。而我也要整装待发，在摸索中前进，在前进中不断摸索，让自己的路走得更远更长！

	彭福原 
                                            2005年6月