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

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

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

最终，所有可能的路径都将形成一个结构。该功能可以测试如下:

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

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