绘制树状图-如何组织存储阵列？

Question

这个问题通常是与语言无关的(虽然这很重要，但我使用的是Java/Processing)。我需要使用一些数据库输出绘制一个树状图形。规则很简单：

图只有一个根。每个Node可以有多个子节点，但只能有一个父节点。

我在思考如何向绘图函数提供数据时遇到了麻烦。我从中获取数据的数据库(它是Rails/MySQL)具有以下结构(我使用伪代码来避免不必要的自引用has_many :通过详细信息)：

Graph
 has_many :nodes

Node
 has_many :siblings
 has_one :parent
 has_many :children

问题是-我应该如何组织放入节点信息的数组，以及如何遍历该数组？一个算法的伪代码将是令人惊讶的。

如果您发现缺少一些信息来回答问题，请让我知道，我很乐意扩展问题/添加数据。

附注:我并不是真的在寻找一些可以为我绘制图表的框架/服务的建议，我实际上需要使用我现有的工具来做到这一点。

谢谢!

编辑：

这就是我现在画图的方式……它从像“0root”，“2Child”，“2Child 2”，“4child_child”这样的数组中一个接一个地获取单词，并重新构造树，假设数组的下一个元素的(整型)前缀大于2，则为子级，如果小于2，则为上一级(父级的同级)。相对于同级的位置是根据数组中具有相同前缀的元素总数计算得出的。我想知道有没有更优雅的方式来做到这一点..？

Graph() { wordList =新ArrayList()；nodeList =新ArrayList()；sibList =新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
  }
}