SWUSTOJ #984 利用二叉树中序及先序遍历确定该二叉树的后序序列

SWUSTOJ #984 利用二叉树中序及先序遍历确定该二叉树的后序序列

SWUSTOJ #984 利用二叉树中序及先序遍历确定该二叉树的后序序列

• 题目
• • 输入
  • 输出
  • 样例输入
  • 样例输出
• 源代码

题目

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果，要求输出其后序遍历结果。

输入

输入数据占2行，其中第一行表示中序遍历结果，第二行为先序遍历结果。

输出

对测试数据，输出后序遍历结果。

样例输入

BFDAEGC
ABDFCEG

样例输出

FDBGECA

源代码

#include <iostream>using namespace std;class treenode
{friend class tree;
public:treenode(char a) :data(a){left = NULL;right = NULL;}
private:char data;treenode* left;treenode* right;
};class tree
{
public:tree(){root = NULL;}void create(treenode* &T, char* pre, char *in, int n);void display(treenode* T);treenode* root;
};void tree::create(treenode* &T, char* pre, char *in, int n)
{if (n <= 0){T = NULL;return;}int k;char * p;T = new treenode(*pre);for (p = in; p < in + n; p++){if (*p == *pre){break;}}				k = p - in;		//记录根的位置，以便于将其分区create(T->left, pre + 1, in, k);//将中序以根为分界 ，左区域create(T->right, pre + k + 1, p + 1, n - k - 1);	//右区域return;
}void tree::display(treenode* T)
{if (T){display(T->left);display(T->right);cout << T->data;}
}int main()
{tree* T = new tree;int n = 0;char arr_pre[100];char arr_in[100];cin >> arr_in;cin >> arr_pre;for (int i = 0; arr_in[i] != '\0'; i++){n++;}T->create(T->root, arr_pre, arr_in, n);T->display(T->root);return 0;
}