title: 生活的烦恼
tags: [数据结构]
题目链接
描述
生活的暑假刚集训开始，他要决心学好字典树，二叉树，线段树和各种树，但生活在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 第三层5 第一层
/
7 4 第二层
/
3 第三层
#include<bits/stdc++.h>
using namespace std;
char s[1000];
int x=0;
typedef struct node
{
char data;
node * lchild;
node * rchild;
int d;
}*Tree;
void build(Tree &T)//由于是要建树，所以每个节点都要保存
{
if(s[x]=='#')
{
T=NULL;
x++;
return ;
}
T=new node;
T->data=s[x++];
build(T->lchild);
build(T->rchild);
}
void shu(node * root,int n)
{
queue<node*>q;
q.push(root);
int op=0;
while(!q.empty())
{
node *t;
t=q.front();
q.pop();
// printf("%c ",t->data);
if(t->d==n)//找到深度为n的
{
if(op==0)
{
printf("%c",t->data);
op=1;
}
else
printf("~%c",t->data);
}
if(t->d>n)break;
if(t->lchild!=NULL)
{
t->lchild->d=t->d+1;
q.push(t->lchild);
}
if(t->rchild!=NULL)
{
t->rchild->d=t->d+1;
q.push(t->rchild);
}
}
}
int main()
{
// freopen("2.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
int num;
int k=0;
memset(s,' ',sizeof(s));
while(1)
{
char a;
scanf(" %c",&a);
if(a=='@')
{
scanf("%d",&num);
break;
}
else s[k++]=a;
}
s[k]=' ';
x=0;
Tree T;
build(T);
T->d=1;
shu(T,num);
puts("");
}
return 0;
}