inoandpos.cpp

本程序为已知二叉树的中序和后序排列

// InoandPos.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 Pos[M],Ino[M];

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

BiTree T;
   
BiTree Build_Sub(BiTree &T,int Pos_Start,int Pos_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表
{
	BiTree lroot,rroot;
	int leftlen,rightlen;
	T=(BiTree)malloc(sizeof(BiTree)); //建根
	T->data=Pos[Pos_End];
	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,Pos_Start,Pos_Start+leftlen-1,In_Start,In_Start+leftlen-1);
		T->lchild=lroot;
	} //建左子树,注意参数表的计算
	else
		T->lchild=NULL;
	if(rightlen)
	{
		rroot=Build_Sub(T->rchild,Pos_End-rightlen,Pos_End-1,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 pos,ino;
	printf("请输入后序序列（以#结束）：\n");
	scanf("%c",&pos);
	int p=0;
	if(pos=='#')
		T=NULL;
	while(pos!='#')
	{
		p++;
		Pos[p]=pos;
		scanf("%c",&pos);
	}
	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");
}