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

Question

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

示例：

图中有2条路径t handle: 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

也许 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 2

一个简单的方法。
您只需要遍历树和一点自定义代码。

有一个名为 tempPath 的列表。你可以把它当作参数或全局变量。
进行树遍历（例如，中序）。每当您在一个节点时，将其添加到末尾的 tempPath 列表中，并在完成此节点后从 tempPath 的末尾删除该节点。
每当你遇到一片叶子时，你就有一个从根到叶子的完整路径，它包含在 tempPath 中。您可以将此列表值打印或复制到另一个数据结构中。

Answer 3

我真的没有看到足够多的代码来使用您定义的 classes。所以我开始编写自己的工作解决方案。

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

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 class 构造一棵树。首先创建一个头 TreeNode，然后根据需要向其添加 child 个节点。然后将头部提交给 TreePaths getPaths 静态函数。

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

的所有 children 都会发生这种情况

最后，所有可能的路径都将在一个结构中结束。这个功能可以测试如下：

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

注意：以上内容足以进行手动测试，但应修改测试函数以进行正确的断言以进行正确的自动化单元测试。

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

Getting all possible paths in a tree structure

java

recursion

tree

ontology

wordnet