在樹上

計算後裔我創建了一個結構來表示這樣一個簡單的樹：在樹上

 A 
    /\ 
    B C 
/\/\ 
    D E F G

的每個節點都是一個記錄這是我裏面的一些字段的自定義類。在下面的例子中，只用包含節點子節點的字段進行簡化。當列表爲空時，我們有一個葉節點。

我的目標是編寫一個函數，返回給定節點的所有後代。

這是我寫的代碼：

 public static void main(String[] args) { 

    HashMap<String, Record> treeMap = new HashMap<String, Record>(); 
    treeMap.put("A", new Record(new LinkedList<String>(Arrays.asList("B","C")))); 
    treeMap.put("B", new Record(new LinkedList<String>(Arrays.asList("D", "E")))); 
    treeMap.put("C", new Record(new LinkedList<String>(Arrays.asList("F", "G")))); 
    treeMap.put("D", new Record(new LinkedList<String>())); 
    treeMap.put("E", new Record(new LinkedList<String>())); 
    treeMap.put("F", new Record(new LinkedList<String>())); 
    treeMap.put("G", new Record(new LinkedList<String>())); 
    System.out.println(descendantsRN("A", treeMap)); 
} 

public static LinkedList<String> descendantsRN(String rn, HashMap<String, Record> map) 
{ 
    LinkedList<String> result = null; 
    if(map.get(rn).getListOfChildren()!= null) 
    { 
     result = map.get(rn).getListOfChildren(); 
     LinkedList<String> children = map.get(rn).getListOfChildren(); 
     for (String child : children) { 
      descendantsRN(child , map); 
     } 
    } 
    return result; 
}

的問題如下：當我之前的例子打印出的後裔，我只得到了B和C，而不是B，C ，d，E，F，G。我不明白爲什麼這是錯的。錯誤在哪裏，我該如何解決？

來源

2017-01-21 user840718

這是一個非常複雜的問題，應該是比較簡單的。您沒有顯示「Record」的來源，但我懷疑它需要大量的重構。 –

記錄並不重要。它總共只有3個字段用字符串填充。我避免讓整個代碼更易讀。 – user840718

由於您忽略遞歸調用descendantsRN所返回的列表，您只會獲得第一級後代。

調用的結果addAll應該可以解決這個問題：

LinkedList<String> result = new LinkedList<String>(); 
LinkedList<String> children = map.get(rn).getListOfChildren(); 
result.addAll(children); 
for (String child : children) { 
    result.addAll(descendantsRN(child , map)); 
} 
return result;

來源

2017-01-21 00:06:05 dasblinkenlight

我試過你的解決方案，但我得到了以下錯誤：線程「主」java.util.ConcurrentModificationException異常。這與LinkedList的錯誤使用有關嗎？謝謝。 – user840718

@ user840718我看到了，您還需要克隆結果。我馬上編輯。 – dasblinkenlight

的問題是在你的for循環。你還記得相同的功能，女巫給出了一個返回聲明。問題在於你沒有做任何回報。
嘗試將結果列表與函數調用的結果一起加入。
我還沒有測試過，但我認爲它應該可以工作。

result.addAll(descendantsRN(child , map));

來源

2017-01-21 00:21:30 Azoth

回答

相關問題