描述

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

输入

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

输出

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

样例输入

21 2 # # 3 # # @ 15 7 3 # # # 4 # # @ 3

样例输出

13

提示

5 第一层
/ \
7 4 第二层
/
3 第三层

看似简单的二叉树，对我这菜鸟真是折磨~~啊

 1 #include<iostream> 2 using namespace std; 3 int j=1; 4 typedef struct Node 5 { 6     char data; 7     Node *left; 8     Node *right; 9 }Node;10 Node* Create()11 {12     char ch;13     cin>>ch;14     Node* root;15 16     if(ch==‘#‘)17         return NULL;18     else19     {20         root=new Node;21         root->data=http://www.mamicode.com/ch;22         root->left=Create();23         root->right=Create();24         return root;25     }26 }27 void createTree(Node *&root)28 {29     char ch;30     cin>>ch;31     if(ch == ‘#‘)32         root = NULL;33     else34     {35         root = new Node;36         if(!root)37             return;38         root->data =http://www.mamicode.com/ ch;39         createTree(root->left);40         createTree(root->right);41     }42 43 }44 45 void print(Node *root, int k, int i)46 {47     if( root )48     {49         if(i == k && j == 1)50         {51             cout<<root->data;52             j++;53             return;54         }55         else if(i == k && j > 1)56         {57             cout<<"~"<<root->data;58             j++;59             return;60         }61         i++;62         print(root->left,k,i);63         print(root->right,k,i);64 65     }66 }67 //void t(Node *root)68 //{69 //    if(root)70 //    {71 //        t(root->left);72 //        cout<<root->data<<" ";73 //        t(root->right);74 //    }75 //}76 int main()77 {78     char data;79     struct Node *root=NULL;80     int n,i;81     cin>>n;82     while(n--)83     {84         createTree(root);85         cin>>data;86         cin>>i;87         print(root,i,1);88         cout<<endl;89         root = NULL;90         j=1;91     }92     return 0;93 }