思路:
都告訴1 是根節點了,直接從1往下搞,隊列層序周遊
解答:
package bupt;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
*@author:Totoro
*@createDate:2020年3月18日下午7:44:15
*/
public class 二叉樹的層數
{
public static point[] tree;
public static int now_n;
public static int[] is_creat=new int[105];
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
int t,n,m,a,b;
t=cin.nextInt();
for(int tt=1;tt<=t;++tt)
{
n=cin.nextInt();
m=cin.nextInt();
tree=new point[m];
Arrays.fill(is_creat,-1);
now_n=0;
while(n--!=0)
{
a=cin.nextInt();
b=cin.nextInt();
if(is_creat[b]==-1)
{
is_creat[b]=now_n;
tree[now_n++]=new point(b);
}
int fa_index=is_creat[b];
if(tree[fa_index].lc==-1)
tree[fa_index].lc=now_n;
else
tree[fa_index].rc=now_n;
tree[now_n]=new point(a);
is_creat[a]=now_n++;
}
for(int i=0;i<now_n;++i)
if(tree[i].v==1)
{
Queue<Integer> qe=new LinkedList<Integer>();
qe.offer(i);
System.out.println("Q"+tt+":");
go(qe);
break;
}
}
}
public static void go(Queue<Integer> qe)
{
Queue<Integer> qee=new LinkedList<Integer>();
int x;
point p;
while(qe.peek()!=null)
{
x=qe.poll();
p=tree[x];
System.out.print(p.v);
if(p.lc!=-1)
qee.offer(p.lc);
if(p.rc!=-1)
qee.offer(p.rc);
if(qe.peek()!=null)
System.out.print(" ");
else
break;
}
System.out.println();
if(qee.peek()!=null)
go(qee);
}
public static class point
{
int lc,rc;
int v;
public point(int v)
{
this.v=v;
lc=-1;
rc=-1;
}
}
}