VIJOS-P1132（求先序遍历，已知中后）

描述

        给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

输入

第一行为二叉树的中序序列 第二行为二叉树的后序序列

输出

一行，为二叉树的先序序列

样例输入

BADC
BDCA

样例输出

ABCD

下面函数名称：PostBtree

函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。

输入参数: BTree & t：二叉树的结点t

          string mid：存储了二叉树的中序序列的字符串

          string post：存储了二叉树的后序序列的字符串

          int lm, int rm：二叉树的中序序列在数组mid中的左右边界

          int lp, int rp：二叉树的后序序列在数组post中的左右边界

#include<iostream>
#include<string>
using namespace std;
typedef struct BTNode{
      char data;
      struct BTNode *lc, *rc;//左，右孩子指针
} *BTree;
void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp);
void Preorder(BTree p);
int main(int argc, char* argv[])
{

    string mid, post;
    BTree root;
    cin >> mid;
    cin >> post;
    PostBtree(root, mid, post, 0, mid.size()-1, 0, post.size()-1);
    Preorder(root);
    return 0;

}
void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp)
{

    t = new BTNode; //构造二叉树根结点
    t->data = post[rp];
    t->lc = t->rc = NULL;
    int pos = lm;
    while (mid[pos] != post[rp])
        pos++;
    int lenL = pos - lm;
    if (pos > lm)//有左孩子，递归构造左子树
        PostBtree(t->lc, mid, post, lm, pos-1, lp, lp+lenL-1);
    if (pos < rm)//有右孩子，递归构造右子树
     PostBtree(t->rc, mid, post, pos+1, rm, lp+lenL, rp-1);

}
//先序遍历
void Preorder(BTree p)
{
       if(p != NULL)
       {
            cout << p->data; //输出该结点
              Preorder(p->lc); //遍历左子树
              Preorder(p->rc); //遍历右子树
       }
}