goal00001111

/*
  Name: 已知中序与后序，或者中序与先序，构造二叉树
  Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
  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;
}

/*
函数名称：PostBtree
函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。
输入参数: BTree & t：二叉树的结点t
          string mid：存储了二叉树的中序序列的字符串
          string post：存储了二叉树的后序序列的字符串
          int lm, int rm：二叉树的中序序列在数组mid中的左右边界
          int lp, int rp：二叉树的后序序列在数组post中的左右边界
*/
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);
}
/*
函数名称：PreBtree
函数功能：给出一棵二叉树的中序与先序序列，构造这棵二叉树。
输入参数: BTree & t：二叉树的结点t
          string mid：存储了二叉树的中序序列的字符串
          string pre：存储了二叉树的先序序列的字符串
          int lm, int rm：二叉树的中序序列在数组mid中的左右边界
          int lp, int rp：二叉树的先序序列在数组post中的左右边界
*/
void PreBtree(BTree & t, string mid, string pre, int lm, int rm, int lp, int rp)
{
    t = new BTNode; //构造二叉树根结点
    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)//有左孩子，递归构造左子树
        PreBtree(t->lc, mid, pre, lm, pos-1, lp+1, lp+lenL);
    if (pos < rm)//有右孩子，递归构造右子树
        PreBtree(t->rc, mid, pre, pos+1, rm, lp+lenL+1, rp);
}

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

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