描述

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

NOJ 1063 生活的烦恼-LMLPHP

 
输入
第一行输入一个数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 ;
}
05-07 15:56