首页 > 代码库 > 华科机考:二叉树遍历

华科机考:二叉树遍历

时间限制:1秒                    空间限制:32768K              

题目描述

二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树;中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入描述: 两个字符串,其长度n均小于等于26。 第一行为前序遍历,第二行为中序遍历。 二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。

 

输出描述: 输入样例可能有多组,对于每组测试样例, 输出一行,为后序遍历的字符串。

输入例子: ABC

              BAC

              FDXEAG

              XDEFAG

 

输出例子: BCA

             XEDGAF

思路:1.通过前序序列找到根节点,然后以此节点为基础将中序序列分为两部分,大家平时这样的题也做过不少,现在是让用程序实现这一过程。

         2.显然应该用递归实现这一过程,但实现递归,最重要的就是传参,这里我们设置4个参数,travel(char pre[],char inorder[],char post[],int length)

         前三个分别对应前序,中序,后序序列,第四个则表示串长。

       

 

         具体分析过程:

         前序:FDXEAG

         后序:XDEFAG 

自己画了一下大致的过程:

 

技术分享

技术分享

大家可以看到以根节点为分界的点,无论是前序还是中序都分布在同一侧诶

具体实现的过程:

                1. 先用一个for循环确定到根在中序序列中的位置,然后就可以对post数组进行赋值(将该值放置在post数组最后)

                2.假设根的下标为i,则左串长度为i,pre数组的首地址为pre+1,inorder数组的首地址不需要移动,post数组的首地址不需要移动

                即:travel(pre+1,inorder,post,i);

                3.右串的长度为length-1-i,pre数组的首地址为pre+i+1,inorder数组的首地址位inorder+i+1,post数组的首地址为post+i;

                4.当length<=0时,为递归出口

代码:

   

#include <iostream>
#include <string.h>
using namespace std;

void travel(char pre[],char inorder[],char post[],int length){
      if(length<=0)
        return;
      int i;
      for(i=0;i<length;i++)
         if(inorder[i]==pre[0])
            break;  
      post[length-1]=pre[0];
      travel(pre+1,inorder,post,i);
      travel(pre+i+1,inorder+i+1,post+i,length-1-i);
}

int main(){
   char pre[30],inorder[30],post[30];
   while(cin>>pre){
   cin>>inorder;
   travel(pre,inorder,post,strlen(pre));
   //post[strlen(pre)]=‘\0‘;
   for(int i=0;i<strlen(pre);i++)
   cout<<post[i];
   cout<<endl;
   }
   return 0;
}

这里需要强调一下,这题如果要用cout或者printf()输出的话,需要在数组最后面加上‘\0‘,因为这题需要输入多组数组诶,当后来的串比前面要短时,就可能会发生错误。

               

华科机考:二叉树遍历