NOJ 1063 生活的烦恼

描述

生活的暑假刚集训开始，他要决心学好字典树，二叉树，线段树和各种树，但生活在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>

 using namespace std;

 int j=;

 typedef struct Node

 {

     char data;

     Node *left;

     Node *right;

 }Node;

 Node* Create()

 {

     char ch;

     cin>>ch;

     Node* root;

     if(ch=='#')

         return NULL;

     else

     {

         root=new Node;

         root->data=ch;

         root->left=Create();

         root->right=Create();

         return root;

     }

 }

 void createTree(Node *&root)

 {

     char ch;

     cin>>ch;

     if(ch == '#')

         root = NULL;

     else

     {

         root = new Node;

         if(!root)

             return;

         root->data = ch;

         createTree(root->left);

         createTree(root->right);

     }

 }

 void print(Node *root, int k, int i)

 {

     if( root )

     {

         if(i == k && j == )

         {

             cout<<root->data;

             j++;

             return;

         }

         else if(i == k && j > )

         {

             cout<<"~"<<root->data;

             j++;

             return;

         }

         i++;

         print(root->left,k,i);

         print(root->right,k,i);

     }

 }

 //void t(Node *root)

 //{

 //    if(root)

 //    {

 //        t(root->left);

 //        cout<<root->data<<" ";

 //        t(root->right);

 //    }

 //}

 int main()

 {

     char data;

     struct Node *root=NULL;

     int n,i;

     cin>>n;

     while(n--)

     {

         createTree(root);

         cin>>data;

         cin>>i;

         print(root,i,);

         cout<<endl;

         root = NULL;

         j=;

     }

     return ;

 }