preandin.cpp

已知二叉树中序遍历和先序遍历序列

// PreandIn.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#include "stdio.h"

#define size 100
#define M 20

int m=1;
char Pre[M],Ino[M];

typedef struct BiNode{
	char data;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

BiTree T;
   
BiTree Build_Sub(BiTree &T,int Pre_Start,int Pre_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表
{
	BiTree lroot,rroot;
	int leftlen,rightlen;
	T=(BiTree)malloc(sizeof(BiTree)); //建根
	T->data=Pre[Pre_Start];
	int i=In_Start;
	while(Ino[i]!=T->data)
		i++;	//在中序序列中查找子树根
	leftlen=i-In_Start;
	rightlen=In_End-i; //计算左右子树的大小
	if(leftlen)
	{
		lroot=Build_Sub(T->lchild,Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1);
		T->lchild=lroot;
	} //建左子树,注意参数表的计算
	else
		T->lchild=NULL;
	if(rightlen)
	{
		rroot=Build_Sub(T->rchild,Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);
		T->rchild=rroot;
	} //建右子树,注意参数表的计算
	else
		T->rchild=NULL;
	return T;
}//Build_Sub 

void Disptree(BiNode *T)
{//输出二叉树
	if(T)
	{
		printf("%c",T->data);
		if(T->lchild || T->rchild)
		{
			if(T->lchild)
			{
				printf("(");
				Disptree(T->lchild);
				if(T->rchild)
				{
					printf(",");
					Disptree(T->rchild);
					printf(")");
				}
				else
				{
					printf(",");
					printf("#");
					printf(")");
				}
			}
			else
			{
				if(T->rchild)
				{
					printf("(");
					printf("#");
					printf(",");
				}
				Disptree(T->rchild);
				printf(")");
			}
		}
	}
}

void main()
{

	char pre,ino;
	printf("请输入先序序列（以#结束）：\n");
	scanf("%c",&pre);
	int p=0;
	if(pre=='#')
		T=NULL;
	while(pre!='#')
	{
		p++;
		Pre[p]=pre;
		scanf("%c",&pre);
	}
	printf("请输入中序序列（以#结束）：\n");
	scanf("%c",&ino);
	int j=-1;
	if(ino=='#')
		T=NULL;
	while(ino!='#')
	{
		j++;
		Ino[j]=ino;
		scanf("%c",&ino);
	}
	int n=p;
	Build_Sub(T,1,n,1,n);
	printf("生成的二叉树为：\n");
	Disptree(T);
	printf("\n");
}