java - 深度优先搜索列表路径到所有端节点

Question

您好，我有一棵树，我想在其中获取从初始(根)节点到所有叶子的路径。

我发现了几种算法，它们列出了图中任意给定两个节点之间的(所有)路径(例如这个 SO 问题: Graph Algorithm To Find All Connections Between Two Arbitrary Vertices )

对于二叉树也存在一种算法 http://techieme.in/print-all-paths-in-a-tree/ 但我在一棵具有各种分支因子的树上工作。

有没有比遍历一次树以获得所有叶子然后对所有叶子与初始节点运行上面的算法更好的方法来实现我想要做的事情？

我正在考虑实现简单的 DFS，通过一些额外的堆栈扩展，该堆栈包含所有节点以及到单个叶子的路径，然后通过遍历这些堆栈列出所有句子。

    ArrayList<GrammarNode> discovered = new ArrayList<GrammarNode>();
    Stack<GrammarNode> S = new Stack<GrammarNode>();


    while (!S.empty()) {
        node = S.pop();
        if (!discovered.contains(node)) {
            discovered.add(node);
            System.out.println(node.getWord.getSpelling().trim());
            for (GrammarArc arc : node.getSuccessors()) {
                S.push(arc.getGrammarNode());
            }
        }
    }

更新: 这样做的问题是人们总是要回到根上才能生成完整的句子。所以我想问题是:如何记住已经完全访问过的节点(这意味着已经探索了所有子节点的位置)？

Answer 1

打印从根到每个叶子的所有路径意味着打印整棵树，所以我只使用一个简单的 DFS 并对每个节点执行以下操作:

• 将其添加到列表/堆栈
• 如果节点有子节点，对子节点重复
• 如果节点是叶子，打印列表/堆栈
• 从链表/栈中弹出节点

例子:

   A
  / \
 B   E
/ \ / \
C D F G

第一步看起来像这样:

• 将 A 放入列表中 -> {A}
• 将 B 放入列表中 -> {A,B}
• 将 C 放入列表 -> {A,B,C}
• 因为 C 是叶子，打印列表 (A,B,C)
• 从列表中删除 C -> {A,B}
• 将 D 放入列表中 -> {A,B,D}
• 因为 D 是叶子，打印列表 (A,B,D)
• ...