p_i_p.cpp

BiTree_Pre_post_in 利用中序遍历及前序遍历（后叙遍历）求后序遍历（前叙遍历） 如果遇到什么问题

//p_i_p.cpp
//uuhorse
//2008.05.20


#include "pip.h"
#include <algorithm>
#include <functional>

//TElemType *find()

Status PreInCreateBT (BiTree & T, TElemType Pre[], TElemType In[], int length)
//利用 中序遍历 及 前序遍历   创建树
{

	if ( length ==0)
	{
		T=NULL;
		return true;
	}

	int lchild_len=0, rchild_len=0;
	TElemType HeadNode = Pre[0];
	TElemType *InHeadPos =NULL;

	T= (BiTNode *) malloc ( sizeof(BiTNode) );
	if (T==NULL)
		return false;

	T->data=HeadNode;
	
	InHeadPos =std::find(In , In +length-1, HeadNode );
	//if (InheadPos == In + length-1)
	
	lchild_len= InHeadPos - In ;
	rchild_len= length-1 - lchild_len;
	//


	PreInCreateBT (T->lchild , Pre+1 , In , lchild_len);


	PreInCreateBT (T->rchild , Pre+1 +lchild_len , In+lchild_len +1, rchild_len);

	return true;

}

Status InPostCreateBT (BiTree & T, TElemType In[], TElemType Post[], int length)
//利用 中序遍历 及 后叙遍历  创建树
{
	if ( length ==0)
	{
		T=NULL;
		return true;
	}

	int lchild_len=0, rchild_len=0;
	TElemType HeadNode = Post[length-1];
	TElemType *InHeadPos =NULL;

	T= (BiTNode *) malloc ( sizeof(BiTNode) );
	if (T==NULL)
		return false;
	T->data=HeadNode;
	
	InHeadPos =std::find(In , In +length-1, HeadNode );
	//if (InheadPos == In + length-1)
	
	lchild_len= InHeadPos - In ;
	rchild_len= length-1 - lchild_len;
	//

	InPostCreateBT (T->lchild , In ,  Post, lchild_len);

	InPostCreateBT (T->rchild , In+lchild_len +1 , Post +lchild_len, rchild_len);

	return true;

}


Status PreInPostModify (BiTree &T)	
//利用中序遍历及前序遍历（后叙遍历）求后序遍历（前叙遍历）
{
	int option=0;
	printf ("请选择 \'0\' 或 \'1\' :\n");
	printf ("0、利用中序遍历及前序遍历求后序遍历\n");
	printf ("1、利用中序遍历及后叙遍历求前叙遍历\n");
	scanf("%d",&option);getchar();
	
	
	if (option==0)//利用中序遍历及前序遍历求后序遍历
	{
		TElemType Pre[MaxSize], In[MaxSize];
		int i=0;
		printf ("请输入前序遍历序列,输入回车键结束:\n");

		while( (Pre[i]=getchar())!='\n' )
			if(Pre[i]!=' ')
				i++;
		Pre[i]='\0';
		
		printf ("请输中序遍历序列:\n");
		i=0;
		while( (In[i]=getchar())!='\n' )
			if(In[i]!=' ')
				i++;
		In[i]='\0';
		
		PreInCreateBT ( T, Pre, In, i);

		printf("得到后序遍历：\n");
		PostOrderTraverse (T);
		printf ("\n");
		
	}
	else if (option==1)		//利用中序遍历及后叙遍历求前叙遍历
	{
		TElemType In[MaxSize], Post[MaxSize];

		int i=0;
		printf ("请输入中序遍历序列,输入回车键结束:\n");

		while( (In[i]=getchar())!='\n' )
			if(In[i]!=' ')
				i++;
		In[i]='\0';
		
		printf ("请输后序遍历序列,输入回车键结束:\n");
		i=0;
		while( (Post[i]=getchar())!='\n' )
			if(Post[i]!=' ')
				i++;
		Post[i]='\0';
		
		InPostCreateBT ( T, In, Post, i);

		printf ("得到前序遍历：\n");
		PreOrderTraverse (T);
		printf ("\n");
	}
	else
	{
		T=NULL;
		printf ("程序退出!");
		return false;
	}
	return true;
}





Status PreOrderTraverse ( BiTree T /*,Status (*Visit)(TElemType e) */) //前序遍历
{

	if (T!=NULL)
	{
		if ( Visit (T) )	//访问根节点
			if (PreOrderTraverse ( T->lchild  ))	//遍历左子树
				if (PreOrderTraverse ( T->rchild ))	//遍历右子树
					return true;
		return false;
	}
	return true;
}

Status InOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) */ )//中序遍历
{
	if (T!=NULL)
	{
		if (InOrderTraverse ( T->lchild  ))	//遍历左子树
			if ( Visit (T) )	//访问根节点
				if (InOrderTraverse ( T->rchild ))	//遍历右子树
					return true;
		return false;
	}
	return true;
}	

Status PostOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) */)//后序遍历
{
	if (T!=NULL)
	{
		if (PostOrderTraverse ( T->lchild  ))	//遍历左子树
			if (PostOrderTraverse ( T->rchild ))	//遍历右子树
				if ( Visit (T) )	//访问根节点
					return true;
		return false;
	}
	return true;
}

Status LevelOrderTraverse ( BiTree T/*,Status (*Visit)(TElemType e) ,int MaxSize*/)//层序遍历
{
	#define MaxSize 100

	BiTree Qu[MaxSize];
	//Qu= (BiTNode **)malloc (sizeof(BiTree));	//定义循环队列，用于存储同层节点
	int front,rear;
	
	front=rear=0;
	if(!Visit (T))				///////////
		return false;
	rear++;
	Qu[rear]= T;
	while (rear!=front)
	{
		front=(front+1)%MaxSize;
		T=Qu[front];
		if (T->lchild!=	NULL)	//左孩子访问成功
		{
			printf(" %c ",T->lchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=T->lchild;
		}
		if (T->rchild!=NULL)
		{
			printf(" %c ",T->rchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=T->rchild;
		}
	}
	printf("\n");
	return true;
}

Status Visit (BiTNode* p)//对节点进行访问输出
{
	if (p==NULL)
	{
		printf("节点p为空，访问失败！\n");
		return false;
	}
	else
	{
		printf(" %c ",p->data);
		return true;
	}
}