最近都被被数据结构弄死了，整天都是树的建立啊，遍历啊，真的受不了了，哎，借这个简单的题发泄下吧，笔者整理了两种方法，希望能够对你有些帮助吧！
hdu acm 1710原题大意：就是给出你树的中序和前序让你输出相应的后序
* 这样的题目应该举一反三，而不是做过了就算了，不然等于没做
* 这个通过建树的方法，在给出中序遍历和按层遍历的时候也可以用
* 先序后序无法推出中序，中序后序推先序可以用递归。
/*hdu acm 1710*/
#include <iostream>
using namespace std ;
const int MaxSize=1000+10 ;
struct node{
int lchild, rchild, num ;
} tree[MaxSize] ;
int flag, root, all, pre[MaxSize], in[MaxSize] ;
void init( int index )
{
tree[index].lchild = tree[index].rchild = -1 ;
}
void dfs( int parent, int son )
{
// 左孩子
if( son < parent )
{
// 左孩子为空，把这个son加为这个节点的左孩子
if( tree[parent].lchild == -1 )
{
init( son ) ;
tree[parent].lchild = son ;
//tree[son].num =
return ;
}
dfs( tree[parent].lchild, son ) ;
}
// 右孩子
else {
if( tree[parent].rchild == -1 )
{
init( son ) ;
tree[parent].rchild = son ;
return ;
}
dfs( tree[parent].rchild, son ) ;
}
}
void construct_tree()
{
int i, j ;
for( i=0; i<all; ++i )
{
if( in[i] == pre[0] )
{
root = i ;
tree[i].num = pre[0] ;
init( i ) ;
break ;
}
}
for( i=1; i<all; ++i )
{
for( j=0; j<all; ++j )
{
if( pre[i] == in[j] )
{
dfs( root, j ) ;
break ;
}
}
}
}
void post( int index )
{
if( tree[index].lchild != -1 )
post( tree[index].lchild ) ;
if( tree[index].rchild != -1 )
post( tree[index].rchild ) ;
if( flag )
cout << " " ;
++flag ;
cout << in[index] ;
}
int main()
{
//freopen("in.txt", "r", stdin ) ;
//freopen("out.txt", "w", stdout ) ;
int i ;
while( cin >> all )
{
for( i=0; i<all; ++i )
{
cin >> pre[i] ;
}
for( i=0; i<all; ++i )
{
cin >> in[i] ;
}
construct_tree() ;
flag = 0 ;
post( root ) ;
cout << endl ;
}
return 0 ;
}
上面的方法是已经 AC过的；还有一种方法虽然代码短点，但不好理解，顺便写在下面把。
#include <iostream>
using namespace std;
int pre[1005],mid[1005];
void printpost(int start1, int start2, int size, bool flag)
{
if(size==1)
{
printf("%hd ",pre[start1]);
return;
}
else if(size<=0)
return;
int i;
for(i=0;i<size && pre[start1]!=mid[start2+i];i++) ;
printpost(start1+1,start2,i,false);
printpost(start1+i+1,start2+i+1,size-i-1,false);
if(flag)
printf("%d\n",pre[start1]);
else
printf("%d ",pre[start1]);
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&pre[i]);
for(i=0;i<n;i++)
scanf("%d",&mid[i]);
printpost(0,0,n,true);
}
return 0;
}
通过上面两种方法应该有助于你对树的遍历的理解吧