题目链接

描述

生活的暑假刚集训开始，他要决心学好字典树，二叉树，线段树和各种树，但生活在OJ上刷题的时候就遇到了一个特别烦恼的问题。那当然就是他最喜欢的二二叉树咯！题目是这样的：给你一颗非空的二叉树，然后再给你一个整数n，让生活输出这颗二叉树的第n(n>0且n<=树的深度)层，出题者为了给生活降低难度，要求两个输出数据之间用'~'隔开。看来我们的出题人很有爱啊！

• 输入
  
  第一行输入一个数N，表示有N组测试数据。接下来N行，每行一个字符串，用'#'表示为空的节点，树的结束标志为'@'。'@'后仅有一个空格，空格后为一个数字，表示生活要输出的二叉树的第几层！

• 输出
  
  每行输出一个字符串，表示给出二叉树的第n层！

• 样例输入
  
  2
  
  1 2 # # 3 # # @ 1
  
  5 7 3 # # # 4 # # @ 3

• 样例输出
  
  1
  
  3

• 提示(第二个测试样例)
  
  5 第一层
  
  /
  
  7 4 第二层
  
  /
  
  3 第三层

  分析：
  
  题目上给出的是二叉树的中序序列，而中序的访问序列是根节点、左子树、右子树，而在构树的时候采用二维数组来模拟。

代码：

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

const int MAXN = 100;

vector<char> G[MAXN];

void print(int n)//打印第n层树

{

    int flag = 0;

    for(int i = 0; i < G[n].size(); i++)

    {

        if(!flag)

        {

            flag = 1;

            putchar(G[n][i]);

        }

        else

            printf("~%c",G[n][i]);

    }

    printf("\n");

}

void build(int x)//递归给每层分类，x表示层数

{

    char tem;

    scanf(" %c",&tem);

     //putchar(tem);

    if(tem == '#')

        return;

    G[x].push_back(tem);

    build(x+1);

    build(x+1);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        for(int i = 0; i < MAXN; i++)

            G[i].clear();

        build(1);

        int op;

        scanf(" @ %d",&op);

        print(op);

    }

    return 0;

}