cpp1.cpp

根据一棵二叉树结点的先根序列和中根序列构造该二叉树

#include<iostream>
#include<string>

using namespace std;

typedef char ElemType;
struct BTreeNode
{
	ElemType data;
	BTreeNode* leftChild;
	BTreeNode* rightChild;
};

void GetString(string &s1,string &s2)
{
	cout<<"请分别输入先根序列和中跟序列:"<<endl;
	cout<<"先跟序列："<<endl;
	cin>>s1;
	cout<<"中跟序列："<<endl;
	cin>>s2;
}

void CreateBTree(BTreeNode* &T,string s1,string s2)
{
	if(s2[0]=='\0')
		T=NULL;
	else
	{
		T=new BTreeNode;
		T->data=s1[0];
		string a1=s1,a2=s1,b1=s2,b2=s2;
		int i,j,k;
		for(i=0;s1[0]!=s2[i];i++)
			a2[i]=s2[i];
		a2[i]='\0';
		for(j=0;j<i;j++)
			a1[j]=s1[j+1];
		a1[j]='\0';
		for(k=0;s2[i]!='\0';i++,k++)
			b2[k]=s2[i+1];
		b1[k]='\0';
		for(k=0;s1[j]!='\0';j++,k++)
			b1[k]=s1[j+1];
		b1[k]='\0';
		CreateBTree(T->leftChild,a1,a2);
		CreateBTree(T->rightChild,b1,b2);
	}
}

void PostOrder(BTreeNode* T )
{
	if(T!=NULL) 
	{
		PostOrder(T->leftChild);
		PostOrder(T->rightChild); 
		cout<<T->data;
	}   
}

int main()
{
	BTreeNode* T=NULL;
	string s1,s2;
	GetString(s1,s2);
	CreateBTree(T,s1,s2);
	cout<<"该二叉树的后序遍历结果为："<<endl;
	PostOrder(T);
	cout<<endl;
	return 0;
}