描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。
输入
第一行为二叉树的中序序列 第二行为二叉树的后序序列
输出
一行,为二叉树的先序序列
样例输入
BADC
BDCA
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); //遍历右子树 } }