樹狀圖 (二) - 有分岔點

李泳霖

承 樹狀圖 (一) - 無分岔點，以類似的解題技巧，完成下列三個有分岔點的範例練習。

範例輸入一

6
3 5
0 1
3 4
1 2
1 3

範例輸出一

根節點: 0
葉節點: 2 4 5
最深距離: 3






範例輸入二

9
7 6
2 4
3 0
7 1
6 8
2 5
3 2
0 7

範例輸出二

根節點: 3
葉節點: 1 4 5 8
最深距離: 4






範例輸入三

10
9 1
2 0
7 4
8 3
9 6
9 8
7 2
7 9
5 7

範例輸出三

根節點: 5
葉節點: 0 1 3 4 6
最深距離: 4

1. import java.io.BufferedReader;
   
2. import java.io.InputStreamReader;
   
3. import java.util.ArrayList;
   
4. 
   
5. 
   
6. public class Ch01 {
   
7.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
8.         String raw[];
   
9.         Node[] node;
   
10.         int root,n;
    
11.         ArrayList<Integer>leaf=new ArrayList<Integer>();
    
12.         Ch01()throws Exception{
    
13.                 n=Integer.parseInt(br.readLine());
    
14.                 node=new Node[n];
    
15. 
    
16.                 for(int i=0;i<n;i++)
    
17.                         node[i]=new Node();
    
18. 
    
19.                 for(int i=0;i<n-1;i++){
    
20.                         raw=br.readLine().split(" ");
    
21.                         int p=Integer.parseInt(raw[0]);
    
22.                         int c=Integer.parseInt(raw[1]);
    
23.                         node[c].parent=p;
    
24.                         node[p].child.add(c);
    
25.                 }
    
26.                 System.out.println("每個節點的父");
    
27.                 for(int i=0;i<n;i++)
    
28.                         System.out.println("node["+i+"]的parent為"+node[i].parent);
    
29.                 System.out.println("每個節點的子");
    
30.                 for(int i=0;i<n;i++)
    
31.                         System.out.println("node["+i+"]的child為"+node[i].child);
    
32. 
    
33.         }
    
34.         class Node{
    
35.                 int parent=-1;
    
36.                 int h=0;
    
37.                 ArrayList<Integer>child=new ArrayList<Integer>();
    
38.         }
    
39.         public static void main(String[] args) throws Exception{
    
40.                 new Ch01();
    
41.         }
    
42. 
    
43. }

複製代碼