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

Question

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

例子：

在图中，有 2 个路径 t 句柄： 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。首先创建一个 head TreeNode，然后根据需要向其添加子节点。然后将头部提交给TreePaths getPaths静态函数。

getPaths 检查 null 后，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

注意：上面的内容对于手动测试来说已经足够了，但是应该修改测试函数以便为正确的自动化单元测试进行正确的断言。