遍历任意树结构中的每个唯一路径(从根到叶)

Question

我有几个清单:

A = ["a0", "a1"]       // the number of lists varies
B = ["b0", "b1", "b2"] // such as the number of elements in a list.
C = ["c1"]
D = ["d0", "d1"]

我将此结构转换为树:

             _____ROOT______
            /               \ 
       ___a0____        ____a1____
      /    |    \      /     |    \
    b0    b1    b2    b0    b1    b2
     |     |     |     |     |     |
    c1    c1    c1    c1    c1    c1
   / |   / |   / |   / |   / |   / |
  d0 d1 d0 d1 d0 d1 d0 d1 d0 d1 d0 d1

我打印树中的每个唯一路径(省略根):

a0 -> b0 -> c1 -> d0
a0 -> b0 -> c1 -> d1
a0 -> b1 -> c1 -> d0
...
a1 -> b2 -> c1 -> d1

我通过以下列方式遍历它来"摧毁"树本身来做到这一点:

public static void delete(Node node) {
  if (node.isLeaf() && !node.isRoot()) {
    Node parent = node.getParent();
    parent.removeChild(node);
    delete(parent);
  }
}

public static void traverse(Node node) {
  if (node.isRoot())
    System.out.println("---");
  else
    System.out.println(node.getName());

  if (node.isLeaf()) {    // I'm still working on
    if (!node.isRoot()) { // removing unnecessary checks
      delete(node);
      traverse(node.getRoot());
    }
  } else {
    Node child = node.firstChild();
    if (null != child)
      traverse(child);
  }
}      

traverse(Node)始终打印树的第一个可用路径(从根到叶),同时delete(Node)剪切已经访问过的树的叶子traverse(Node).

这按预期工作,但我渴望找到一种解决方案,以前面描述的方式遍历树而不会破坏它.如果有办法做到这一点,那么我有兴趣遍历这个相同的结构,但以图形的形式来减少冗余.

Answer 1

好.我认为你的意思是你想要找到从根到叶子的每条路径.

然后(一个未优化的版本)

void traverse (Node root) {
  // assume root != NULL
  traverse (root, new LinkedList<Node>());
}

private void traverse (Node root, LinkedList<Node> path) {
  path.add(root);
  if (root.isLeaf()) {
    print path;
  }
  else {
    for each node of root {
      traverse (node, new LinkedList<Node>(path));
    }
  }
}