codeup|问题A:复原二叉树

题目描述小明在做数据结构的作业其中一题是给你一棵二叉树的前序遍历和中序遍历结果要求你写出这棵二叉树的后序遍历结果。输入输入包含多组测试数据。每组输入

题目描述 小明在做数据结构的作业其中一题是给你一棵二叉树的前序遍历和中序遍历结果要求你写出这棵二叉树的后序遍历结果。 输入 输入包含多组测试数据。每组输入包含两个字符串分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。 输出 对于每组输入输出对应的二叉树的后续遍历结果。 样例输入 Copy DBACEGF ABCDEFG BCAD CBAD 样例输出 Copy ACBFGED CDAB

代码

#include#include#include#includeusing namespace std;const int maxn 50;struct node {char data;node *lchild;node *rchild;};char pre[maxn], in[maxn], post[maxn];//分别代表前序、中序、后序int n;//结点个数node *create(int preL, int preR, int inL, int inR) {//当前线序序列区间为[preL,preR],中序序列区间为[inL,inR]if (preL > preR) return NULL;node *root new node;//新建一个结点用来存放二叉树的根节点root->data pre[preL];int k;for (k inL; k lchild create(preL 1, preL numLeft, inL, k - 1);//右子树的先序区间为[prenumLeft1,preR],中序序列为[k1,inR]root->rchild create(preL numLeft 1, preR, k 1, inR);return root;//返回根节点地址}int num 0;//已输出结点的个数//void BFS(node* root){// queue q;//注意队列里是地址// q.push(root);//将根节点地址入队// while(!q.empty()){// node* nowq.front();//取出队首元素// q.pop();// printf("%c",now->data);// num;// if(numlchild!NULL) q.push(now->lchild);//左子树非空// if(now->rchild!NULL) q.push(now->rchild);//右子树非空// }//}void postorder(node *root) {if (root NULL) return;postorder(root->lchild);postorder(root->rchild);printf("%c", root->data);}int main() {node *root;while (cin >> pre >> in) {int len strlen(pre);root create(0, len - 1, 0, len - 1);postorder(root);printf("\n");}return 0;}