数据结构中的经典问题之一就是根据二叉树的某种遍历序列重建二叉树，比如给出前序和中序序列，但是要求输出后序遍历的结果。

这里仅仅帖一份根据前序和中序遍历重建二叉树的代码吧（要输出后序遍历的结果，只要添加一个后序遍历函数即可），正好是POJ 2255的答案。

#include <iostream>

#include

<map>

#include

<utility>

#include

<functional>

#include

<string>

#include

<stack>

using namespace

std;

typedef char

Type;

struct

Node

{

     Node( Node *t ) : data( t->data ), lChild( t->lChild ), rChild( t->

rChild ) {}

     Node( Type d ) : data( d ), lChild( NULL ), rChild( NULL ) {}

    struct Node*

lChild;

    struct Node*

rChild;

     Type data;

};

Node *rebuildFromPreInOrder( string &preOrder, string &

inOrder )

{

    // preOrder and inOrder always have equal length.

    if ( preOrder.size() == 0

)

        return

NULL;

    if ( preOrder.size() == 1

)

        return new Node( preOrder[0

] );

    // get the root

     Node *root = new Node( preOrder[0

] );

    //

divide inOrder sequence into two sub sequences

    // by the first node of preOrder sequence.

     size_t rootPos = inOrder.find( preOrder[0

] );

    string left_sub_inorder = inOrder.substr( 0

, rootPos );

    string right_sub_inorder = inOrder.substr( rootPos + 1

);

     size_t left_size =

left_sub_inorder.size();

    

    // divide preOrder sequence into two sub sequences by their length.

    string left_sub_preorder = preOrder.substr( 1

, left_size );

    string right_sub_preorder = preOrder.substr( left_size + 1

);

    // recursive rebuilding and connect with root

     root->lChild =

rebuildFromPreInOrder( left_sub_preorder, left_sub_inorder );

     root->rChild =

rebuildFromPreInOrder( right_sub_preorder, right_sub_inorder );

    return

root;

}

void PostOrder( Node *root, void (*visit)(Node*

) )

{

     stack<Node*>

s;

     Node *cur =

root;

     Node *visited =

NULL;

    while( ! s.empty() || cur !=

NULL )

     {

        while( cur !=

NULL )

         {     s.push( cur ); cur = cur->

lChild; }

         cur = s.top();  // check but no visit.

        

if( cur->rChild == visited || cur->rChild ==

NULL )

         {

             visit( cur ); s.pop();

             visited =

cur;

             cur = NULL; // no current node, must pop.

         }

        else

             cur

= cur->

rChild;

     }

}

void visit( Node *

t )

{

     cout<<t->

data;

}

int

main()

{

    while ( !

cin.eof() )

     {

        string pre, in

;

         cin>>pre>>in

;

         Node *root = rebuildFromPreInOrder( pre, in

);

         PostOrder( root, visit );

         cout<<

endl;

     }

    

    return 0

;

}