程序3：二叉树构造.cpp

构造一个二叉树的基本算法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define M 50
typedef struct node
{
	char data; 
	struct node *lchild,*rchild;
}JD;
typedef struct 
{
	JD * data[M]; 
	int top;
}TEMP;
TEMP *s;
int flag=0;             /*构造正误标志*/
void main()
{
	TEMP *createemptystacks();
	JD *createtree(char pre[],char in[],int i);
	void preorder(JD *t,char pre[]);
	void inorder(JD *t,char in[]);
	char pre[M],in[M];
	int i,j,k;
	JD *tr;
	for(j=1;j<=2;j++)
	{
		for(k=1;k<=75;k++)
			printf("*");
		printf("\n");
	}
	for(j=1;j<=22;j++)
		printf("*");
    printf("欢迎您使用该软件,版权归白俊所有");
	for(j=1;j<=22;j++)
		printf("*");
	printf("\n");
	for(j=1;j<=2;j++)
	{
		for(k=1;k<=75;k++)
			printf("*");
		printf("\n");
	}   
	printf("请输入先序序列：\n");
	gets(pre);
	printf("请输入中序序列：\n");
	gets(in);
	i=strlen(pre);
	tr=createtree(pre,in,i);
	preorder(tr,pre);
	printf("\n");
	inorder(tr,in);
	printf("\n");
	printf("构造正确吗？\n\n");
	printf("按任意键显示判断结果：\n");
	getch();
	if(flag==1) 
		printf("对不起，您的构造错误！\n");
	else
		printf("恭喜您，您的构造正确！\n");
	printf("\n");
	for(j=1;j<=2;j++)
	{
		for(k=1;k<=75;k++)
			printf("*");
		printf("\n");
	}
	for(j=1;j<=30;j++)
		printf("*");
    printf("谢谢您的使用！");
	for(j=1;j<=31;j++)
		printf("*");
	printf("\n");
	for(j=1;j<=2;j++)
	{
		for(k=1;k<=75;k++)
			printf("*");
		printf("\n");		
	}  
	printf("\n\n\n\n\n\n"); 
}

TEMP *createemptystacks()  /*建立空栈*/
{
	s=(TEMP*)malloc(sizeof(TEMP));
	s->top=0;
	return s;
} 
JD *createtree(char pre[],char in[],int i) /*创建二叉树*/
{
	JD *t;
	t=(JD*)malloc(sizeof(JD));
	int ma,mb,mc,md,j,j1,j2,k;
	char t1[M],t2[M],s1[M],s2[M];
	ma=0; mb=i; 
	t->data=pre[0];
   	j=0;
	while(in[j]!=pre[0]) j++;
	mb=j-1; 
	j1=j; 
	j2=i-j-1;
	for(k=1;k<=mb-ma+1;k++) 
		t1[k-1]=pre[k]; /*t1中存放在前序序列中左子树的元素*/
	t1[k-1]='\0';
	for(k=ma;k<mb+1;k++)/*t2中存放在中序序列中左子树的元素*/
		t2[k-ma]=in[k];
	t2[k-ma]='\0';
	k=mb-ma+2;
	mc=mb+2;
	md=i-1;
	while(k<i) /*s1中存放在前序序列中右子树的元素*/
	{
		s1[k-mb+ma-2]=pre[k];
		k++;
	}
	s1[k-mb+ma-2]='\0';
	k=mc;
    while(k<=md) /*s2中存放在中序序列中右子树的元素*/
	{		
       s2[k-mc]=in[k]; 
       k++;
	}
	s2[k-mc]='\0';
	if(j1==0)    /*中序根结点前没有元素，则左子树为空*/
		t->lchild=NULL;
	else 
		t->lchild=createtree(t1,t2,j1);/*t1存放前半部分的前序序列，t2存放前半部分的中序序列*/
	if(j2==0) /*中序根结点后没有元素，则右子树为空*/
		t->rchild=NULL;
	else 
		t->rchild=createtree(s1,s2,j2);/*s1存放后半部分的前序序列，s2存放后半部分的中序序列*/
	return (t);
}

void preorder(JD *t,char pre[]) /*非递归算法*/
{
	TEMP *st;
	JD *p;
	int i=0;
	if(t==NULL) return; /*空树返回*/
	st=createemptystacks(); /*建立空栈*/
	p=t;                    /*p指向根结点*/
	printf("先序遍历二叉树得：\n");
	while(st->top!=0||p)
	{
	  while(p!=NULL) /*p不为空*/
	  {
		  printf("%c",p->data);
		  if(p->data!=pre[i])  /*错误跳出*/
		  {
			  flag=1;
			  break;
		  }
		  i++;
		  if(p->rchild!=NULL)
			  st->data[st->top++]=p->rchild; /*右子树根结点进栈*/
		  p=p->lchild; /*一直沿左子树直到空*/
	  }
	  if(st->top!=0) /*判断栈不为空*/
	  {
		  p=st->data[st->top-1];/*取栈顶元素*/
		  st->top--;  /*出栈*/
	  }
	}/*结束条件为栈空且p指向空*/
}
void inorder(JD *t,char in[])   /*非递归算法*/
{
	TEMP *st;
	JD *p;
	int i=0;
	if(t==NULL) return;  /*空树返回*/
	st=createemptystacks();  /*建立空栈*/
	p=t;      /*p指向根结点*/
	printf("中序遍历二叉树得：\n");
	while(st->top!=0||p)
	{
		while(p!=NULL) 
		{
		    st->data[st->top++]=p;  /*根结点进栈*/
			p=p->lchild;
		}
		if(st->top!=0)
		{
			p=st->data[st->top-1];  /*取栈顶元素*/
			st->top--;   /*出栈*/
			printf("%c",p->data);
			if(p->data!=in[i])
			{
				flag=1;
				break;
			}
			i++;
			p=p->rchild;
		}
	}

}