繪製樹形圖 - 如何組織存儲陣列？

Question

這個問題通常與語言無關（儘管如此，我正在使用Java/Processing）。我需要使用一些數據庫輸出來繪製一個樹形圖。規則很簡單：

圖只有一個Root。 每個節點可以有幾個孩子，但只有一個父母。

我在繞過如何將數據提供給繪圖函數時遇到了麻煩。我從獲取數據的數據庫（它的Rails/MySQL的）具有以下結構（我使用僞代碼，以避免不必要的自我指涉的has_many：通過細節）：

Graph 
has_many :nodes 

Node 
has_many :siblings 
has_one :parent 
has_many :children 

的問題是 - 我應該如何組織陣列我將節點信息放入以及如何循環訪問數組？算法的僞代碼將會很棒。

如果您發現某些信息缺少答案，請告訴我，我很樂意擴大問題/添加數據。

P.S.我並不是在尋找可以爲我繪製圖形的框架/服務的建議，實際上我需要使用我現有的工具來完成這些工作。

謝謝！

編輯：

這就是我現在怎麼繪製圖形...它源自like [「0root」，「2child」，2child2' ，‘4child_child’]數組需要一個字一個和重建樹假設如果數組的下一個元素的（int）前綴大於2，那麼它是一個孩子，如果它小於2，那麼它是一個級別（父級的兄弟）。相對於兄弟姐妹的位置是根據數組中具有相同前綴的元素的總數來計算的。我想知道是否有更優雅的方式來做到這一點..？

圖（）{ wordList = new ArrayList（）; nodeList = new ArrayList（）; sibList = new ArrayList（）; }

Integer sibNumber(int idx<char>) { 
    Map<Integer, Integer> sibCount = new HashMap<Integer, Integer>(); 
    for (Integer sibling: sibList) { 
     Integer count = sibCount.get(sibling); 
     sibCount.put(sibling, (count==null) ? 1 : count+1); 
    } 
    Integer result = sibCount.get(idx); 
    return result; 
    } 


    void update(String wrd) { 
    wordList.add(wrd); 

    String word = wrd; 
    String[][] m = matchAll(wrd, "(\\d*)"); 
    int index = (int) m[0][0]; 
    char number = (char) index; 
    sibList.add(index); 
// println(wrd); 
    word = word.replaceAll(number,""); 
    Integer siblingsNum = sibNumber(index); 
    if (sibList.size()>=2) { 
     lastIndex = sibList.get(sibList.size()-2); 
     int indexDiff = index-lastIndex; 
     if (indexDiff != 0) { 
     for (int i=sibList.size()-1; i>0; i--) { 
      if (index-sibList.get(i) == 2) { 
      parNode = nodeList.get(i); 
      break; 
      } 
     } 
     } 
    } 
    if (index == 2) { 
     parNode = nodeList.get(0); 
    } 

    node = new Node(word, index, siblingsNum, parNode); 
    nodeList.add(node); 

    } 

    void clean() { 
    nodeList = new ArrayList<Node>(); 
    sibList = new ArrayList<Integer>(); 
    } 


    void display() { 
    for (int i = 0; i < nodeList.size(); i++) { 
     nd = nodeList.get(i); 

     if (nd.parent != null) { 

     stroke(255, 0, 0); 
     VerletSpring2D spring=new VerletSpring2D(nd.origin,nd.parent.origin,80,0.01); 
     physics.addParticle(nd.origin); 
     physics.addSpring(spring); 
     line(nd.origin.x+nd.w/2, nd.origin.y, nd.parent.origin.x+nd.w/2, nd.parent.origin.y+nd.parent.h); 
     } 
     nd.display(); 
    } 
    } 
} 

Answer 1

您是否必須使用數組？這個問題的自然解決方案是實現一個'Node'類，它有子節點的引用。這適用於遞歸算法，這將允許您（例如）找到特定的節點。 然後您需要首先引用根節點。

public class Node { 
    private Node parent; 
    private List<Node> children; 

    public Node findNode(String nodeName) { 
    // Is it this node? 
    // Iterate through all child nodes, calling findNode on each 
    } 
}