在树状结构中获取所有可能的路径

Question

我需要在树中循环以获取所有可能的路径，在我的代码中，我只获得第一个路径的问题！

例如：

在该图中，有2条路径吨处理：1-2-3-4-5-6和1-2-3-7-8，但我无法得到两个，我刚刚检索1-2-3-4-5-6！

我的代码：

在主：

for (String key : synset.keySet()) { // looping in a hash of Concept and it's ID 
     System.out.println("\nConcept: " + key + " " + synset.get(key)); 
     List<Concept> ancts = myOntology.getConceptAncestors(myOntology.getConceptFromConceptID(synset.get(key))); // this function retreives the root of any node. 

     for (int i = 0; i < ancts.size(); i++) { 
      System.out.print(ancts.get(i).getConceptId() + " # "); 
      System.out.print(getChilds(ancts.get(i).getConceptId()) + " -> "); // here, the recursive function is needed to navigate into childs.. 
     } 
     System.out.println(""); 
    } 

建议。功能：

public static String getChilds(String conId) 
{ 
    List<Concept> childs = myOntology.getDirectChildren(myOntology.getConceptFromConceptID(conId)); // get all childs of a node 
    if(childs.size() > 0) 
    { 
     for (int i = 0; i < childs.size(); i++) { 
      System.out.print(childs.size() + " ~ " + childs.get(i).getConceptId() + " -> "); 
      return getChilds(childs.get(i).getConceptId()); 
     } 
    } 
    else 
     return "NULL"; 
    return "final"; 
} 

Answer 1

我真的没有看够你的代码中使用您所定义的类。所以我去写自己的工作解决方案。

在下面的代码，这个问题是用解决递归：

public class TreeNode { 
    private String id; 
    private TreeNode parent; 
    private List<TreeNode> children; 

    public TreeNode(String id) { 
     this.id = id; 
     this.children = new LinkedList<>(); 
    } 

    public void addChild(TreeNode child) { 
     this.children.add(child); 
     child.setParent(this); 
    } 

    public List<TreeNode> getChildren() { 
     return Collections.unmodifiableList(this.children); 
    } 

    private void setParent(TreeNode parent) { 
     this.parent = parent; 
    } 

    public TreeNode getParent() { 
     return this.parent; 
    } 

    public String getId() { 
     return this.id; 
    } 
} 

public class TreePaths { 
    private static List<List<TreeNode>> getPaths0(TreeNode pos) { 
     List<List<TreeNode>> retLists = new ArrayList<>(); 

     if(pos.getChildren().size() == 0) { 
      List<TreeNode> leafList = new LinkedList<>(); 
      leafList.add(pos); 
      retLists.add(leafList); 
     } else { 
      for (TreeNode node : pos.getChildren()) { 
       List<List<TreeNode>> nodeLists = getPaths0(node); 
       for (List<TreeNode> nodeList : nodeLists) { 
        nodeList.add(0, pos); 
        retLists.add(nodeList); 
       } 
      } 
     } 

     return retLists; 
    } 

    public static List<List<TreeNode>> getPaths(TreeNode head) { 
     if(head == null) { 
      return new ArrayList<>(); 
     } else { 
      return getPaths0(head); 
     } 
    } 
} 

要使用上面的代码中，树必须使用TreeNode类构成。首先创建一个头TreeNode，然后根据需要添加子节点。然后将头部提交到TreePaths getPaths静态功能。

getPaths检查为空后，将调用内部getPaths0函数。在这里，我们通过尝试尽快到达所有叶节点来遵循深度优先方法。一旦找到叶节点，将只创建一个仅包含此叶节点的List，并在列表集合中返回。这个叶节点的父节点将被添加到列表的开头，这将再次被放入列表集合中。这将发生在父母的所有孩子身上。

最后，所有可能的路径都会以单一结构结束。

public class TreePathsTest { 
    TreeNode[] nodes = new TreeNode[10]; 

    @Before 
    public void init() { 
     int count = 0; 
     for(TreeNode child : nodes) { 
      nodes[count] = new TreeNode(String.valueOf(count)); 
      count++; 
     } 
    } 

    /* 
    * 0 - 1 - 3 
    *  - 4 
    * - 2 - 5 
    *  - 6 
    *  - 7 - 8 
    *   - 9 
    */ 
    private void constructBasicTree() { 
     nodes[0].addChild(nodes[1]); 
     nodes[0].addChild(nodes[2]); 
     nodes[1].addChild(nodes[3]); 
     nodes[1].addChild(nodes[4]); 
     nodes[2].addChild(nodes[5]); 
     nodes[2].addChild(nodes[6]); 
     nodes[2].addChild(nodes[7]); 
     nodes[7].addChild(nodes[8]); 
     nodes[7].addChild(nodes[9]); 
    } 

    @Test 
    public void testPaths() { 
     constructBasicTree(); 
     List<List<TreeNode>> lists = TreePaths.getPaths(nodes[0]); 
     for(List<TreeNode> list : lists) { 
      for(int count = 0; count < list.size(); count++) { 
       System.out.print(list.get(count).getId()); 
       if(count != list.size() - 1) { 
        System.out.print("-"); 
       } 
      } 
      System.out.println(); 
     } 
    } 
} 

这将打印出：

0-1-3 
0-1-4 
0-2-5 
0-2-6 
0-2-7-8 
0-2-7-9 

注：上述是足够的手动测试，但测试功能应该被修饰以做适当的适当的断言这个函数可以如下测试自动化单元测试。

Answer 2

也许在getChilds()这个代码段中存在的问题：

for (int i = 0; i < childs.size(); i++) { 
     System.out.print(childs.size() + " ~ " + childs.get(i).getConceptId() + " -> "); 
     return getChilds(childs.get(i).getConceptId()); 
} 

---

的for loop不能发挥作用，它总是return getChilds(childs.get(0).getConceptId()); 也许这不是你想要的。

Answer 3

一个简单的方法。
所有你需要的是遍历树和一点自定义代码。

• 有一个名为tempPath的列表。您可以将其作为参数或全局变量。
• 做树遍历（例如inorder）。无论何时您在某个节点上，都会将其添加到tempPath列表的最后，并且在完成此节点时，将该节点从tempPath的末尾删除。
• 无论何时遇到树叶，您都有一个完整路径从根目录包含在tempPath中。您可以打印或将此列表值复制到另一个数据结构中。