tree.cpp

该程序的功能为已知二叉树中序遍历和后序遍历序列

#include "stdio.h"
#include "malloc.h"
#define MAX 20
char Post[MAX],Ind[MAX]; //假设前序序列和中序序列已经分别储存在数组Pre和In中
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Build_Sub(int Pos_Start,int Pos_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表
{
	int i = 0,leftlen = 0,rightlen = 0;
	BiTree sroot,lroot,rroot;
	sroot = lroot = rroot = (BiTNode*)malloc(sizeof(BiTNode)); //建根
	sroot->data = Post[Pos_End];
	for(i = In_Start;Ind[i] != sroot->data;i++); //在中序序列中查找子树根
	leftlen = i - In_Start;
	rightlen = In_End - i; //计算左右子树的大小
	if(leftlen)
	{
		lroot = Build_Sub(Pos_Start,Pos_Start +leftlen-1,In_Start,In_Start+leftlen-1);
		sroot->lchild = lroot;
	} //建左子树,注意参数表的计算
	else
		sroot->lchild = NULL;
	if(rightlen)
	{
		rroot = Build_Sub(Pos_Start + leftlen,Pos_End - 1,In_End-rightlen+1,In_End);
		sroot->rchild = rroot;
	} //建右子树,注意参数表的计算
	else
		sroot->rchild = NULL;
	return sroot; //返回子树根
}//Build_Sub 
void translevel(BiTree &T)
  {  
	struct node
	{ 
		BiTree vec[MAX];
		int f,r; 
	} q;
	q.f = 0;
	q.r = 0;                                  //置队列为空队列
	if (T != NULL) 
		printf("%4c",T->data);
	q.vec[q.r] = T;                        //结点指针进入队列
	q.r = q.r + 1;
	while (q.f < q.r)               //队列不为空
	{
		T = q.vec[q.f];             //队头出队列
		q.f = q.f + 1;
		if(T->lchild != NULL)       //输出左孩子，并入队列
		{ 
			printf("%4c",T->lchild->data); 
			q.vec[q.r] = T->lchild;
			q.r = q.r + 1;
		}
		if(T->rchild != NULL)      //输出右孩子，并入队列
		{ 
			printf("%4c",T->rchild->data);
			q.vec[q.r] = T->rchild;
			q.r = q.r + 1;
		}
	}
}  
void main()
{
	int total = 0,i = 0;
    BiTree T1;
	T1 = (BiTNode*)malloc(sizeof(BiTNode));
	T1->lchild = T1->rchild = NULL;
	printf("请输入序列长度(小于20):");
	scanf("%d",&total);
	fflush(stdin);
	printf("请输入中序序列:\n");
    for(i = 0;i < total;i++)
	{
		scanf("%c",&Ind[i]);
		fflush(stdin);
	}
	printf("请输入后序序列:\n");
	for(i = 0;i < total;i++)
	{
		scanf("%c",&Post[i]);
		fflush(stdin);
	}
	T1 = Build_Sub(0,total - 1,0,total - 1); //初始调用参数,n为树结点总数
    printf("层次遍历二叉树结果：\n");
    translevel(T1);
	printf("\n");
}