/*
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é)點
}
}