题目1078：二叉树遍历
题目描述： 二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入： 两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。输出： 输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。样例
输入： ABC BAC FDXEAG XDEFAG 样例输出： BCA XEDGAF来源： 2006年清华大学计算机研究生机试真题
--------------------------------------------------------
解析
由前序遍历和中序遍历求后序遍历，这要求考生对三种遍历方式都有掌握。这里要用到前序遍历的根结点第一个被取出，而中序遍历的左子树在根结点之前取出、右子树在根结点之后取出，这两个性质。
C++实现如下
#include <iostream> #include <string> //1078：二叉树遍历 using namespace std; //结点类 struct Node { Node * lchild; Node * rchild; char c; }; //重建后续排序二叉树 Node * rebuild(string s1, string s2) { //建立根结点 Node * t=NULL; //一定要初始化为NULL，不然报错 if(s1.size()>0){ t=new Node; t->c=s1[0]; t->lchild=NULL; t->rchild=NULL; } if(s1.size()>1){ //寻找根结点在中序遍历中的位置 int root; for(int i=0; i<s2.size(); i++){ if(s2[i]==t->c){ root=i; break; } } //左子树重建 string qianxu_left=s1.substr(1, root); //注意substr的用法，第二个参数是子字符串长度 string zhongxu_left=s2.substr(0, root); t->lchild=rebuild(qianxu_left, zhongxu_left); //右子树重建 string qianxu_right=s1.substr(root+1, s1.size()-root-1); string zhongxu_right=s2.substr(root+1, s2.size()-root-1); t->rchild=rebuild(qianxu_right, zhongxu_right); } return t; } //后序遍历：左右根 void houxu(Node * t) { //左子树非空，遍历左子树 if(t->lchild!=NULL) houxu(t->lchild); //右子树非空，遍历右子树 if(t->rchild!=NULL) houxu(t->rchild); //取出该结点的值 cout<<t->c; } int main() { string s1, s2; while(cin>>s1>>s2){ Node * t=rebuild(s1, s2); houxu(t); cout<<endl; } return 0; } 运行结果Accepted 内存：1520KB 代码长度：1465B 耗时：10MS
转载于:https://www.cnblogs.com/hankai/p/4471415.html
