小虎的二叉树

小虎的二叉树

时间: 1ms        内存:128M

描述:

 小虎的《数据结构》老师留了一项作业:要求写出所画二叉树的层次遍历序列、先序遍历序列、中序遍历序列和后序遍历序列。聪明的小虎很快就写出了层次遍历序列和中序遍历序列。这时,中国国足战胜韩国的捷报传来,激动不已的小虎克制不住自己的情绪欢呼了一场。欢呼过后,小虎发现作业题不见了,他现在只记着二叉树的层次遍历序列和中序遍历序列。你能帮小虎写出先序遍历序列和后序遍历序列吗?
  二叉树的节点用从“A”开始的大写字母表示,节点数最大不超过26

输入:

输入数据包含N(1≤N≤20)个测试样例。
  每个测试样例包含两行,分别为层次遍历序列和中序遍历序列。

输出:

 对于每组测试样例,输出数据包含两行,分别为先序遍历序列和后序遍历序列。

示例输入:

2
CBA
BCA
BACDE
DAEBC

示例输出:

CBA
BAC
BADEC
DEACB

提示:

参考答案(内存最优[1092]):

#include<stdio.h>
#include<string.h>
char a[100],b[100];
int k;
void print1(int n)
{
   if(n>k)return;
   else
   {
       print1(2*n);
       print1(2*n+1);
     printf("%c",a[n]);
   }
}
void print2(int n)
{
   if(n>k)return;
   else
   {
       printf("%c",a[n]);
       print2(2*n);
       print2(2*n+1);
   }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    while(n--)
    {
       scanf("%s\n%s",a,b);
       k=strlen(a);
       for(i=k;i>=1;i--)
        a[i]=a[i-1];
      print2(1);
      printf("\n");
      print1(1);
      printf("\n");
    }
    return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<string.h>
char a[100],b[100];
int k;
void print1(int n)
{
   if(n>k)return;
   else
   {
       print1(2*n);
       print1(2*n+1);
     printf("%c",a[n]);
   }
}
void print2(int n)
{
   if(n>k)return;
   else
   {
       printf("%c",a[n]);
       print2(2*n);
       print2(2*n+1);
   }
}
int main()
{
    int n,i;
    scanf("%d",&n);
    while(n--)
    {
       scanf("%s\n%s",a,b);
       k=strlen(a);
       for(i=k;i>=1;i--)
        a[i]=a[i-1];
      print2(1);
      printf("\n");
      print1(1);
      printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注