樹狀圖 (一) - 無分岔點

李泳霖

樹狀圖分析的其中一種方法為 深度優先搜尋演算法 (DFS)，我們可利用此演算法來找出樹狀結構中，節點間的關係以及自根部開始最深的距離。

但在程式競賽或APCS檢定中若遇到類似的題目，老師並不建議使用 DFS 來解題。原因是 DFS 為遞迴的結構，遞迴結構在對效率極度要求的程式競賽或APCS檢定中，非常容易發生 StackOverFlowError、TLE、MLE 等疑難雜症。

因此對於樹狀圖分析這類的考題，老師會帶同學們以從葉節點往根節點走訪的思維來解題。當然，依然會提供 DFS 解法的程式碼給同學們參考。

下面的這個例子為一無分岔點的樹狀圖，輸入分為兩部分，第一部分為共有幾個成員，第二部分為所有關係。請同學們試著找出在這樣的一個樹狀結構中，根節點是誰、葉節點是誰、最深的距離是多少？

範例輸入

6
0 3
1 0
5 4
2 1
3 5

範例輸出

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

1. import java.io.BufferedReader;
   
2. import java.io.IOException;
   
3. import java.io.InputStreamReader;
   
4. 
   
5. public class P1 {
   
6.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
7.         String raw[];
   
8.         int n,root,leaf;
   
9.         Node node[];
   
10.         P1() throws Exception{
    
11.                 n=Integer.parseInt(br.readLine());
    
12.                 node=new Node[n];
    
13.                 for(int i=0; i<n; i++)
    
14.                         node[i]=new Node();
    
15.                 for(int i=0; i<n-1; i++){
    
16.                         raw=br.readLine().split(" ");
    
17.                         int p=Integer.parseInt(raw[0]);
    
18.                         int c=Integer.parseInt(raw[1]);
    
19.                         node[c].parent=p;
    
20.                         node[p].child=c;
    
21.                 }               
    
22.                 for(int i=0; i<n; i++){
    
23.                         System.out.println(i+"'s parent:"+node[i].parent);
    
24.                         System.out.println(i+"'s child:"+node[i].child);
    
25.                 }
    
26.         }
    
27.        
    
28.         public static void main(String[] args) throws Exception {
    
29.                 new P1();
    
30.         }
    
31. }
    
32. class Node{
    
33.         int parent=-1, child=-1, n=0;
    
34. }

複製代碼