/*
  Name: 已知中序與后序，或者中序與先序，構(gòu)造二叉樹
  Copyright: 始發(fā)于goal00001111的專欄；允許自由轉(zhuǎn)載，但必須注明作者和出處
  Author: goal00001111
  Date: 08-12-08 11:42
  Description:
描述 Description      
給出一棵二叉樹的中序與后序排列。求出它的先序排列。
給出一棵二叉樹的中序與先序排列。求出它的后序排列。
*/

#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 PreBtree(BTree & t, string mid, string pre, int lm, int rm, int lp, int rp);
void Preorder(BTree p);  //先序遍歷
void Postorder(BTree p); //后序遍歷

int main(int argc, char* argv[])
{
    string pre, mid, post;
    BTree root1, root2;
    
    cout << "輸入中序序列" << endl;
    cin >> mid;
    cout << "輸入后序序列" << endl;
    cin >> post;
    PostBtree(root1, mid, post, 0, mid.size()-1, 0, post.size()-1);
    Preorder(root1);
    cout << endl;
    
    cout << "輸入前序序列" << endl;
    cin >> pre;
    PreBtree(root2, mid, pre, 0, mid.size()-1, 0, pre.size()-1);
    Postorder(root2);
    
    system("pause");
    return 0;
}

/*
函數(shù)名稱：PostBtree
函數(shù)功能：給出一棵二叉樹的中序與后序序列，構(gòu)造這棵二叉樹。
輸入?yún)?shù): BTree & t：二叉樹的結(jié)點t
          string mid：存儲了二叉樹的中序序列的字符串
          string post：存儲了二叉樹的后序序列的字符串
          int lm, int rm：二叉樹的中序序列在數(shù)組mid中的左右邊界
          int lp, int rp：二叉樹的后序序列在數(shù)組post中的左右邊界
*/
void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp)
{
    t = new BTNode; //構(gòu)造二叉樹根結(jié)點
    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)//有左孩子，遞歸構(gòu)造左子樹
        PostBtree(t->lc, mid, post, lm, pos-1, lp, lp+lenL-1);
    if (pos < rm)//有右孩子，遞歸構(gòu)造右子樹
        PostBtree(t->rc, mid, post, pos+1, rm, lp+lenL, rp-1);
}
/*
函數(shù)名稱：PreBtree
函數(shù)功能：給出一棵二叉樹的中序與先序序列，構(gòu)造這棵二叉樹。
輸入?yún)?shù): BTree & t：二叉樹的結(jié)點t
          string mid：存儲了二叉樹的中序序列的字符串
          string pre：存儲了二叉樹的先序序列的字符串
          int lm, int rm：二叉樹的中序序列在數(shù)組mid中的左右邊界
          int lp, int rp：二叉樹的先序序列在數(shù)組post中的左右邊界
*/
void PreBtree(BTree & t, string mid, string pre, int lm, int rm, int lp, int rp)
{
    t = new BTNode; //構(gòu)造二叉樹根結(jié)點
    t->data = pre[lp];
    t->lc = t->rc = NULL;
    
    int pos = lm;
    while (mid[pos] != pre[lp])
        pos++;
    int lenL = pos - lm;
    if (pos > lm)//有左孩子，遞歸構(gòu)造左子樹
        PreBtree(t->lc, mid, pre, lm, pos-1, lp+1, lp+lenL);
    if (pos < rm)//有右孩子，遞歸構(gòu)造右子樹
        PreBtree(t->rc, mid, pre, pos+1, rm, lp+lenL+1, rp);
}

//先序遍歷
void Preorder(BTree p)
{
    if(p != NULL)
    {
        cout << p->data; //輸出該結(jié)點
        Preorder(p->lc); //遍歷左子樹
        Preorder(p->rc); //遍歷右子樹
    }
}

//后序遍歷
void Postorder(BTree p)
{
    if(p != NULL)
    {
        Postorder(p->lc); //遍歷左子樹
        Postorder(p->rc); //遍歷右子樹
        cout << p->data; //輸出該結(jié)點
    }
}