#include<stdio.h>
#include<iostream.h>
typedef struct nodes
{
	char ch;
	int flag;
	int left,right;
}nodetype;
void pred(nodetype B[],int root)
{
	cout<<B[root].ch << " ";
	if (B[root].left!=0)
		pred(B,B[root].left);
	if (B[root].right!=0)
		pred(B,B[root].right);

}
void postbtree(char A[],nodetype B[],int n)
{
	int i,j,k,t,root;
	k=1;
	while (A[n]!=B[k].ch)
		k++;
	root=k;
	for (i=n-1;i>=1;i--)
	{
		j=1;
		t=k;
		while (A[i]!=B[j].ch)
			j++;
		while (t!=0)
			if (B[j].flag<B[t].flag)
				if (B[t].left==0)
				{
					B[t].left=j;
					t=0;
				}
				else
					t=B[t].left;
				else if (B[t].right==0)
				{
					B[t].right=j;
					t=0;
				}
				else
					t=B[t].right;
	}
	pred (B,root);

}
void main()
{
	int n=7,i;
	char A[9]="0cbfegda";
	char str[]="0cbaefdg";
	nodetype B[9];
	
	for (i=1;i<=n;i++)
	{
		B[i].ch=str[i];
		B[i].left=B[i].right=0;
		B[i].flag=i;
	}
	cout << "中序序列:";
		for (i=1;i<8;i++)
			cout <<str[i]<< " ";
		cout <<endl;
		cout << "后序序列:";
		for (i=1;i<8;i++)
			cout <<A[i]<< " ";
		cout <<endl;
		cout << "構造二叉樹:" << endl;
		cout << "先序序列:";
		postbtree(A,B,n);
		cout <<endl;

}