遍历任意的树结构每一个独特的路径（从根到叶） [英] Traverse every unique path (from root to leaf) in an arbitrary tree structure

问题描述

我有几个列表：

  A = [A0，A1] //名单的数量变化
B = [B0，B1，B2] //如在一个列表中的元素的数量。
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  - ＆GT; B0  - ＆GT; C1  - ＆GT; D0
A0  - ＆GT; B0  - ＆GT; C1  - ＆GT; D1
A0  - ＆GT; B1  - ＆GT; C1  - ＆GT; D0
...
A1  - ＆GT; B2  - ＆GT; C1  - ＆GT; D1
 

我被破坏树本身同时穿越它以如下方式这样做

公共静态无效删除（节点node）{   如果（node.isLeaf（）＆安培;＆安培;！node.isRoot（））{     节点的父= node.getParent（）;     parent.removeChild（节点）;     删除（父）;   } } 公共静态无效移动（节点node）{   如果（node.isRoot（））     的System.out.println（---）;   其他     的System.out.println（node.getName（））;   如果（node.isLeaf（））{//我还在努力     如果（！node.isRoot（））{//删除不必要的检查       删除（节点）;       遍历（node.getRoot（））;     }   } 其他 {     子节点= node.firstChild（）;     如果（NULL！=儿）       遍历（子）;   } }

移动（节点）始终打印树的第一个可用路径（从根到叶），而删除（节点）的削减已经访问了移动（节点）。

的叶子

这按预期工作，但我渴望找到一个解决方案来遍历pviously描述方式不破坏它的$ P $树。 如果有一种方法可以做到这一点，然后我很想遍历此相同的结构，但在图的形式，以减少冗余。

解决方案

确定。我想你实际上意味着要找到每一个路径从根到叶。

然后（一个未优化的版本）

 无效移动（节点根）{
  //假设根！= NULL
  遍历（根，新的LinkedList＆LT;节点＆GT;（））;
}

私人无效移动（节点根，LinkedList的＆LT;节点＆GT;路径）{
  path.add（根）;
  如果（root.isLeaf（））{
    打印路径;
  }
  其他 {
    为根的每个节点{
      移动（节点，新的LinkedList＆LT;节点＆GT;（路径））;
    }
  }
}
 

I have several lists:

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"]

I convert this structure into a tree:

             _____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

I'm printing every unique path in the tree (omitting the root):

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

I'm doing this by "destroying" the tree itself while traversing it in the following way:

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) always prints the first available path of the tree (from root to leaf) while delete(Node) cuts leafs of the tree that is already visited by traverse(Node).

This works as intended, but I'm keen to find a solution to traverse the tree in the previously described way without destroying it. If there's a way to do this then I'd be interested to traverse this same structure, but in the form of a graph to reduce redundancy.

解决方案

OK. I think you actually mean that you want to find every path from root to a leaf.

Then (a un-optimized version)

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));
    }
  }
}

这篇关于遍历任意的树结构每一个独特的路径（从根到叶）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！