2012.网研院.Problem B.二叉树的层数

女爷i 2023-07-21 13:27 10阅读 0赞

**题目描述**  
老师有一个问题想考考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

这么写a了是因为样例都是顺序输入的，如果节点数不是按大小输入的，可以用vector记录每层节点，顺序加入即可。

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
    	int t,n,m,a,b;
    	int dp[105];
    	cin>>t;
    	int num;
    	for(num=1; num<=t; num++) { 
    		memset(dp,0,sizeof(dp));
    		dp[1]=1;//根节点深度为1
    		cin>>n>>m;
    		int maxp=1;
    		while(n--) { 
    			cin>>a>>b;//b->a
    			dp[a]=dp[b]+1;
    			if(maxp<dp[a]) { 
    				maxp=dp[a];
    			}
    		}
    		cout<<"Q"<<num<<":"<<endl;
    		for(int i=1; i<=maxp; i++) { 
    			int flag=0;
    			for(int j=1; j<=m; j++) { 
    				if(dp[j]==i) { 
    					if(flag==1) { 
    						cout<<" ";
    					}
    					cout<<j;
    					flag=1;
    				}
    			}
    			cout<<endl;
    		}
    	}
    }