202665.cpp

来自「数据结构（清华版）」· C++ 代码 · 共 89 行

#include<iostream.h>
typedef char TElemtype ;


//创建结构体===========================================================================
typedef struct BiTNode
{
	TElemtype data;
	BiTNode *lchild,*rchild,*parent;
} *BiTree;



//根据先序排列及中序排列创建二叉数=====================================================
BiTree BuiltBiTree(char Pre[],char In[],int Pre_Start,int Pre_End,int In_Start,int In_End)
{
		
	int leftlen,rightlen;
	BiTree T,Tl,Tr;
	T=new BiTNode;
	if(!T) return NULL;
	T->data=Pre[Pre_Start];
	for (int i=In_Start;In[i]!=T->data;i++)
		leftlen=i-In_Start;
	rightlen=In_End-i; //计算左右子树的大小

	//建左子树---------------------------------------------------------------------
	if(leftlen!=0)
	{
		Tl=BuiltBiTree( Pre,In,Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1);
		T->lchild=Tl;
	} 
	else T->lchild=NULL;
	//建右子树---------------------------------------------------------------------
	if(rightlen!=0)
	{//cout<<1;
		Tr=BuiltBiTree(Pre,In,Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);
		T->rchild=Tr;
	} 	
	else T->rchild=NULL;

	return T;
}


//======================================================================================
BiTree  BuiltBiTree(char Pre[],char In[])
{

	
	return BuiltBiTree(Pre,In,1,11,1,11);

}

/*
void visit(TElemtype m)
{
	
	cout<<m<<"  ";
}
//广义二叉树输出函数
void preorderlists(BiTree T,void visit(TElemtype))
{
	if(T) 
	{
		visit(T->data);
		if(T->lchild||T->rchild)
		{
			cout<<'(';
			preorderlists(T->lchild,visit);
			cout<<',';
			preorderlists(T->rchild,visit);
			cout<<')';
		}
	}
	else cout<<'#';
}*/

//主函数==============================================================================
void main()
{
	BiTree T;
	TElemtype  Pre[]={'e','b','a','d','c','f','h','g','i','k','j'};
	TElemtype  In[]={'a','b','c','d','e','f','g','h','i','j','k'};
//	TElemtype  Pre[]={' '};
//	TElemtype  In[]={' '};
	BuiltBiTree(Pre,In);
//	preorderlists(T, visit);
}