题目
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示)。
输入输出格式
输入格式:
2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。 输出格式: 1行,表示一棵二叉树的先序。思路
首先,一点基本常识,给你一个后序遍历,那么最后一个就是根(如ABCD,则根为D)。
因为题目求先序,意味着要不断找根。 中序ACGDBHZKX,后序CDGAHXKZB,首先可找到主根B; 那么我们找到中序遍历中的B,由这种遍历的性质,可将中序遍历分为ACGD和HZKX两棵子树, 那么对应可找到后序遍历CDGA和HXKZ(从头找即可) 从而问题就变成求1.中序遍历ACGD,后序遍历CDGA的树 2.中序遍历HZKX,后序遍历HXKZ的树; 接着递归,按照原先方法,找到1.子根A,再分为两棵子树2.子根Z,再分为两棵子树。 就按这样一直做下去(先输出根,再递归); 模板概括为step1:找到根并输出 step2:将中序,后序各分为左右两棵子树; step3:递归,重复step1,2;Code
#include#include #include using namespace std;void beford(string in,string after){ if (in.size()>0){ char ch=after[after.size()-1]; cout< >inord;cin>>aftord;//读入 beford(inord,aftord);cout<