如何在散列表中保存樹結構？

一個二維數組關係[N] [2]表示節點之間的關係，對於爲例關係[0]等於{2,4}，所以有一個adjancency關係在節點2和節點4之間，並且不包含循環關係。

我想救樹結構中一個HashMap，所以我試着寫我的代碼如下圖所示：

Map<Integer, LinkedList<Integer>> graph = new HashMap<Integer, LinkedList<Integer>>(); 
    for (int i = 0; i < n; i++) { 
     int A = relation[i][0]; 
     int B = relation[i][1]; 
     if (graph.get(A) == null) { 
      List<Integer> tempList = new LinkedList(); 
      tempList.add(B); 
      graph.put(A, tempList); 
     } else { 
      graph.get(A).add(B); 
     } 
     if (graph.get(B) == null) { 
      List<Integer> tempList = new LinkedList(); 
      tempList.add(A); 
      graph.put(B, tempList); 
     } else { 
      graph.get(B).add(A); 
     } 
    }

appearently它不工作，但我不知道如何解決它可以，有人幫助我？謝謝！

來源

2017-04-11 Qingyuan Zhu

你能給輸入的例子，預期與實際輸出？ –

從技術上講，你可以做'graph.put（0，tree）;'它將被存儲在一個HashMap中。雖然我確定那不是你想要的，哈哈。 – byxor

你能解釋一下用例嗎？也許有比在散列圖中存儲樹更好的解決方案。例如，也許你需要一個樹狀結構來照原樣使用，但同時節點有一些ID需要保存在另一個結構中（例如：HashMap），以便快速檢索節點。 – andreim

代碼的工作原理（我測試過）除了有一個小的打字錯誤。

Map<Integer, LinkedList<Integer>>

宣告爲是，地圖中的值應該是一些LinkedList。

但在這裏，你把一些List：

List<Integer> tempList = //[...]; 
[...] 
//Compiler will complain that tempList is a List but a LinkedList is expected. 
graph.put(A, tempList);

所以可以創建一些鏈表是這樣的：

LinkedList<Integer> tempList = new LinkedList<>();

或聲明您Map薩姆List需要的值：

Map<Integer, List<Integer>>

注意：從Java 8開始，你可以這樣使用Map.computeIfAbsent：

Map<Integer, LinkedList<Integer>> graph = new HashMap<>(); 
for (int i = 0; i < n; i++) { 
    int A = relation[i][0]; 
    int B = relation[i][1]; 
    graph.computeIfAbsent(A, k-> new LinkedList<>()).add(B); 
    graph.computeIfAbsent(B, k-> new LinkedList<>()).add(A); 
}

來源

2017-04-11 12:54:46

我剛剛添加一個'computeIfAbsent'的例子，當你的編輯來了雖然:) –

感謝您的幫助，我解決了這個問題，通過核心故障〜不錯的滾刀！ –

試試吧。即使處理情況下，當陣列不允許定義邊緣多次（這可能是可能的）：

//   1 
//  /| \ 
//  2 3 4 
// // \ \ 
//  5 6 7 8 
// 
public static void main(String[] args) { 
    int[][] tree = new int[][] { 
      {1, 2}, {1, 3}, {1, 4}, 
     {2, 5}, {3, 6}, {3, 7}, {4, 8} }; 

    Map<Integer, List<Integer>> map = new HashMap<>(); 
    for (int[] node : tree) { 
     addEdge(map, node[0], node[1]); 
     addEdge(map, node[1], node[0]); 
    } 

    System.out.println(map); 
} 

private static void addEdge(Map<Integer, List<Integer>> map, int key, int value) { 
    List<Integer> edges = map.computeIfAbsent(key, k -> new LinkedList<>()); 
    if (! edges.contains(value)) edges.add(value); 
}

輸出

{1=[2, 3, 4], 2=[1, 5], 3=[1, 6, 7], 4=[1, 8], 5=[2], 6=[3], 7=[3], 8=[4]}

來源

2017-04-11 13:08:57 Harmlezz

感謝您的幫助！新的技術得到了！ –

如何在散列表中保存樹結構？

回答

相關問題