首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7422

重建二叉树 给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。 时间限制:1000 内存限制:65536 输入 输入可能有多组,以EOF结束。 每组输入包…

重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。

时间限制:1000

内存限制:65536

输入

输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入,用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include&lt;stdio.h&gt; #include&lt;string.h&gt; void bulid(int n,char s1[],char s2[])//n是树的节点数,s1是记录先序遍历,s2中序遍历  {      if(n&lt;=0)  return;//没有节点了,找到边界return       int p=strchr(s2,s1[0])-s2;      // strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址       //所以p是 s1[0]第一次出现在s2中的位置      bulid(p,s1+1,s2);      //数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...      //以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点       //s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)      bulid(n-p-1,s1+p+1,s2+p+1);      //数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)      //以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点      //s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点 )       printf("%c",s1[0]);//输出  } int main() {      char s1[10007],s2[10007];//s1是树的前序遍历,s2是树的中序遍历      while(scanf("%s %s",s1,s2)!=EOF)//多组数据       {          bulid(strlen(s1),s1,s2);           printf("\n");//记得输出\n       }      return 0; } /* 先序遍历第一个节点一定是根节点。 中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。 后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。 */</pre><p><br/></p>
这道题暂未补解析。