学步园

#include <iostream>
#include <stack>
#include <queue>
#include <utility>
#include <assert.h>
using namespace std;


typedef struct node
{
	char data;
	node *left;
	node *right;
}BiNode,*BiTree;


int CreateBiTreeByPreAndMid(BiTree &root,char *front,char *middle,int len)
{
	assert(len!=0);
	root->data=front[0];
	int i;
	for(i=0;i<len;i++)
	{
		if(middle[i]==root->data)
			break;
	}
	if(i!=0)
	{
		root->left=new BiNode;
		CreateBiTreeByPreAndMid(root->left,front+1,middle,i);
	}
	else
		root->left=NULL;
	if(i!=len-1)
	{
		root->right=new BiNode;
		CreateBiTreeByPreAndMid(root->right,front+i+1,middle+i+1,len-i-1);
	}
	else
		root->right=NULL;
	return 1;
}


int CreateBiTreeByMidAndPost(BiTree &t,char *midOrder,char*postOrder,int len)
{
	assert(len!=0);
	t->data=postOrder[len-1];
	int i;
	for(i=0;i<len;i++)
	{
		if(midOrder[i]==t->data)
			break;
	}
	if(i!=0)
	{
		t->left=new BiNode;
		CreateBiTreeByMidAndPost(t->left,midOrder,postOrder,i);
	}
	else
		t->left=NULL;
	if(i!=len-1)
	{
		t->right=new BiNode;
		CreateBiTreeByMidAndPost(t->right,midOrder+i+1,postOrder+i,len-i-1);
	}
	else
		t->right=NULL;
	return 1;
 }


void Visit(BiNode &binode)
{
	cout<<binode.data;
}


void PreOrder(BiTree &t)
{
	stack<BiNode*> s;
	BiNode *p=t;
	if(p==NULL)
		return;
	s.push(p);
	while(!s.empty())
	{
		p=s.top();
		Visit(*p);
		s.pop();
		if(p->right)
			s.push(p->right);
		if(p->left)
			s.push(p->left);
	}
}


void PreOrder2(BiTree &t)
{
	stack<BiNode*> s;
	BiNode *p=t;
	while(p!=NULL || !s.empty())
	{
		while(p!=NULL)
		{
			Visit(*p);
			s.push(p);
			p=p->left;
		}
		if(!s.empty())
		{
			p=s.top();
			s.pop();
			p=p->right;
		}
	}
}


void MidOrder(BiTree &t)
{
	stack< pair<BiNode*,int> >s;
	int unUsed;
	BiNode*p=t;
	s.push(make_pair(p,1));
	while(!s.empty())
	{
		p=s.top().first;
		unUsed=s.top().second;
		s.pop();
		if(unUsed)
		{
			if(p->right)
				s.push(make_pair(p->right,1));
			s.push(make_pair(p,0));
			if(p->left)
				s.push(make_pair(p->left,1));
		}
		else
		{
			Visit(*p);
		}
	}
}


void MidOrder2(BiTree &t)
{
	stack<BiNode*>s;
	BiNode *p=t;
	while(p!=NULL || !s.empty())
	{
		while(p!=NULL)
		{
			s.push(p);
			p=p->left;
		}
		if(!s.empty())
		{
			p=s.top();
			Visit(*p);
	    	s.pop();
	    	p=p->right;
		}
	}
}


void PostOrder(BiTree &t)
{
	stack< pair<BiNode*,int> >s;
	int unUsed;
	BiNode*p=t;
	s.push(make_pair(p,1));
	while(!s.empty())
	{
		p=s.top().first;
		unUsed=s.top().second;
		s.pop();
		if(unUsed)
		{	
			s.push(make_pair(p,0));
			if(p->right)
				s.push(make_pair(p->right,1));	
			if(p->left)
				s.push(make_pair(p->left,1));	
		}
		else
		{
			Visit(*p);
		}
	}
}


void PostOrder2(BiTree &t)
{
	stack<BiNode*>s;
	BiNode*p=t,*pre=NULL;
	s.push(p);
	while(!s.empty())
	{
		p=s.top();
		if((p->left==NULL&&p->right==NULL)
			||(pre!=NULL&&(p->left==pre||p->right==pre)))
		{
			Visit(*p);
			s.pop();
			pre=p;
		}
		else
		{
			if(p->right)
				s.push(p->right);
			if(p->left)
				s.push(p->left);
		}
	}
}


void LeverOrder(BiTree &t)
{
	queue<BiNode*> q;
	BiNode *p=t;
	q.push(p);
	while(!q.empty())
	{
		p=q.front();
		Visit(*p);
		q.pop();
		if(p->left)
			q.push(p->left);
		if(p->right)
			q.push(p->right);
	}


}


int main(int argc,char *argv[])
{
	char str1[100],str2[100];
	BiTree t=new BiNode;
	freopen("PreAndMid.txt","r",stdin);
	cin>>str1>>str2;
	assert(strlen(str1)==strlen(str2));
	CreateBiTreeByPreAndMid(t,str1,str2,strlen(str1));
	PreOrder(t);
	cout<<endl;
	PreOrder2(t);
	cout<<endl;
	MidOrder(t);
	cout<<endl;
	MidOrder2(t);
	cout<<endl;
	PostOrder(t);
	cout<<endl;
	PostOrder2(t);
	cout<<endl;
	LeverOrder(t);
	cout<<endl;
	return 0;
}