在樹狀結構中獲取所有可能的路徑

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中。您可以打印或將此列表值複製到另一個數據結構中。