学步园

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

输入

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

输出

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

样例输入

2
1 2 # # 3 # # @ 1
5 7 3 # # # 4 # # @ 3

样例输出

1
3

在这里我重述下题目，因为这个作者说的有点不清楚。

输入数据为二叉树的先序遍历顺序，其中#空结点的标志。@为树的结束标志（多此一举，给定了树的序列，一定是到此正好建立完毕。。@后的一个数学为要输入二叉树的第几层。。二叉树的层数从1开始计数）

输出的要求，输入这棵二叉的第n层的结点。如果结点的数据 大于1，则应该每二个结点之间用'~'分开

另外我想说的本题的坑:是本题的树的结点编号不一定是数字，但是一定是一个字符。但是我这里使用了字符串统一处理，使程序的鲁棒性更强。

其实本题考的就是二叉的重建与层次遍历（指定层次的）。。树的重建数据结构课本上有。。指定层次的层次遍历只需使用一个变量记录当前层次即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<sstream>
using namespace std;
const int mx=11000;
//二叉树链表存储结构 
typedef struct BiNode{
	string data;
	struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
//总感觉此题建立二叉树时的时候需要使用递归。果然是这样，见书本p131页。。
string temp;
int flag=0;
int createBiTree( BiTree &r){
	flag=0;
	cin>>temp;
	if(temp.length()==1 && temp[0]=='#') r=NULL ;
	else{ 
		 flag=1;
	}
	if(flag){
		r=new BiTNode;
		r->data=temp;
		createBiTree(r->lchild);
		createBiTree(r->rchild);
		flag=0;
	}
	return 1;
}//递归建树完毕。
queue<string> ans; 
//对于只输出二叉树上的某一层，我们只需要记录相应的层数即可。 
void preOrder(BiTree &T,int leval,int p_leval){
	if(T==NULL) return ;
	if(leval==p_leval){
		ans.push(T->data);
		return ;
	}
	preOrder(T->lchild,leval+1,p_leval);
	preOrder(T->rchild,leval+1,p_leval); 
}//访问某一层树。从1开始计数。 
int n;
int main()
{
	int N;
	cin>>N;
	while(N--){
		string ch;
		BiTree T;
		createBiTree(T);
		cin>>ch;
		cin>>n;
		//下面对棵树进行层次遍历。 只输出每第n层的信息。
		preOrder(T,1,n); 
		int stop=ans.size();
		if(stop>1){
			for(int i=0;i<stop-1;i++){
				cout<<ans.front()<<"~";
				ans.pop();
			}
			cout<<ans.front()<<endl;
			ans.pop();
		}
		else{
			cout<<ans.front()<<endl;
			ans.pop();
		}
	}
    return 0;
}