题目描述
老师有一个问题想考考mabo，但是mabo不会，所以想请你来帮帮忙。
问题如下：
给一个二叉树
请把这个棵二叉树按层来打印。如果为相同层，需要从左到右打印。一个节点是先添加左节点后添加右节点，即添加顺序与输入顺序一致。
输入格式
首先输入一个整数T，表示一共有T组数据 0<T<=10
再输入两个整数N,M(0<=N,M<=100)
表示下面有N行，这个树有M个节点(1号节点是这棵树的根节点)
每一行两个整数a,b(1<=a,b<=M)
表示节点a的父亲是节点b
输出格式
对于每组
先输出一行 "Qi:"表示第i个问题
然后接下来输出每个问题二叉树每层的节点，在同一层的节点用空格分开，同一层输出在一行（每一行末尾没有空格），不同的层输出在不同行（入下面Sample Ouput所示）
输入样例
2
4 5
2 1
3 1
4 2
5 4
1 2
2 1输出样例
Q1:
1
2 3
4
5
Q2:
1
2判断二叉树的同一层可由深度depth实现, *lnext, *rnext保存的分别是左子节点和右子节点的地址
P.S. 前面最后的输出部分也可以由C++的STL queue内pop(), push()来实现
/*
USER_ID: test#birdstorm
PROBLEM: 100
SUBMISSION_TIME: 2014-03-02 11:54:13
*/
#include <stdio.h>
#include <stdlib.h>
#define For(i,m,n) for(i=m;i<n;i++)
#define MAXN 105typedef struct tree{int depth, name;struct tree *lnext, *rnext;
}tree;main()
{int i, j, T, t, n, m, x, y, flag;int c[MAXN];struct tree d[MAXN];scanf("%d",&T);For(t,1,T+1){scanf("%d%d",&n,&m);For(i,0,m+1){d[i].depth=0;d[i].lnext=d[i].rnext=NULL;}d[1].depth=1;For(i,0,n){scanf("%d%d",&x,&y);d[x].name=x;d[y].name=y;if(d[y].lnext==NULL) d[y].lnext=&d[x];else d[y].rnext=&d[x];d[x].depth=d[y].depth+1;}printf("Q%d:\n",t);i=j=c[1]=1; flag=1;while(i<=j){if(d[c[i]].lnext!=NULL) c[++j]=(*d[c[i]].lnext).name;if(d[c[i]].rnext!=NULL) c[++j]=(*d[c[i]].rnext).name;if(i>1) putchar(d[c[i]].depth!=flag?'\n':' ');printf("%d",d[c[i]].name);flag=d[c[i]].depth;i++;}puts("");}return 0;
}