数据结构第七章实验题3-由遍历序列构造二叉树

数据结构第七章实验题3-由遍历序列构造二叉树 实验题3-由遍历序列构造二叉树

目的：领会二叉树的构造过程以及构浩二叉树的算法设计

内容：内容:编写一个程序exp7-3.cpp,实现由先序序列和中序序列以及由中序序列和后序序列构造一棵二叉树的功能(二叉树中的每个结点值为单个字符),要求以括号表示和凹人表示法输出该二叉树,并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJHLKMNEAFCGI”和后序遍历序列“DJLNMKHEBFIGCA”进行验证。

#include
#include
#include
#define MaxSize 100
#define MaxWidth 40
typedef char ElemType;
typedef struct node
{
	ElemType data;//数据元素
	struct node *lchild;//指向左孩子
	struct node *rchild;//指向右孩子
}BTNode;
//输出二叉树
 void DispBTNode(BTNode *b)
 {
 	if(b!=NULL)
 	{
 		printf("%c",b->data);
 		if(b->lchild!=NULL||b->rchild!=NULL)
 		{
 			printf("(");
 			DispBTNode(b->lchild);
 			if(b->rchild!=NULL)
 				printf(",");
 			DispBTNode(b->rchild);
 				printf(")");
		 }
	 }
  } 
//销毁二叉树
 void DestroyBTNode(BTNode *&b)
 {
 	if(b!=NULL)
 	{
 		DestroyBTNode(b->lchild);
 		DestroyBTNode(b->rchild);
 		free(b);
	 }
  } 
BTNode *CreateBT1(char *pre,char *in,int n) 
{
	BTNode *s; 
	char *p;
	int k;
	if (n<=0) return NULL;
	s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树节点*s
	s->data=*pre;
	for (p=in;plchild=CreateBT1(pre+1,in,k);
	s->rchild=CreateBT1(pre+k+1,p+1,n-k-1);
	return s; 
}
BTNode *CreateBT2(char *post,char *in,int n,int m)
{
	BTNode *s; 
	char *p,*q,*maxp;
	int maxpost,maxin,k;
	if (n<=0) return NULL;
	maxpost=-1;
	for (p=in;pmaxpost)
		{
		maxpost=k;
		maxp=p;
		maxin=p-in;
		}
	}
	s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树节点*s
	s->data=post[maxpost];
	s->lchild=CreateBT2(post,in,maxin,m);
	s->rchild=CreateBT2(post,maxp+1,n-maxin-1,m);
	return s;
}
void DispBTNode1(BTNode *b)//以凹入表表示法输出一棵二叉树
{
	BTNode *St[MaxSize],*p;
	int level[MaxSize][2],top=-1,n,i,width=4;
	char type;
	if (b!=NULL)
	{
		top++;
		St[top]=b;//根节点入栈
		level[top][0]=width;
		level[top][1]=2;//2表示是根
		while (top>-1)
		{	
			p=St[top];//退栈并凹入显示该节点值
			n=level[top][0];
			switch(level[top][1])
			{
				case 0:type='L';break;//左节点之后输出(L)
				case 1:type='R';break;//右节点之后输出(R)
				case 2:type='B';break;//根节点之后前输出(B)
			}
		for (i=1;i<=n;i++)//其中n为显示场宽,字符以右对齐显示
			printf("");
			
		printf("%c(%c)",p->data,type);
		for (i=n+1;i<=MaxWidth;i+=2)
			printf("--");
		printf("n");
		top--;
		if (p->rchild!=NULL)
		{//将右子树根节点入栈
			top++;
			St[top]=p->rchild;
			level[top][0]=n+width;//显示场宽增width
			level[top][1]=1;//1表示是右子树
		}
		if (p->lchild!=NULL)
		{//将左子树根节点入栈
			top++;
			St[top]=p->lchild;
			level[top][0]=n+width;//显示场宽增width
			level[top][1]=0;//0表示是左子树
		}
		}
	}
}
int main()
{
	BTNode *b;
	ElemType pre[]="ABDEHJKLMNCFGI";
	ElemType in[]="DBJHLKMNEAFCGI";
	ElemType post[]="DJLNMKHEBFIGCA";
	b=CreateBT1(pre,in,14);
	printf("先序序列:%sn",pre);
	printf("中序序列:%sn",in);
	printf("构造一棵二叉树b:n");
	printf(" 括号表示法:");
	DispBTNode(b);
	printf("n");
	printf(" 凹入表示法:n");
	DispBTNode1(b);printf("nn");
	printf("中序序列:%sn",in);
	printf("后序序列:%sn",post);
	b=CreateBT2(post,in,14,14);
	printf("构造一棵二叉树b:n");
	printf(" 括号表示法:");
	DispBTNode(b);
	printf("n");
	printf(" 凹入表示法:n");
	DispBTNode1(b);
	printf("n");
	DestroyBTNode(b); 
}