本文介绍了深度优先搜索列出指向所有末端节点的路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
您好,我有一棵树,我想在其中获取从初始(根)节点到所有叶子的路径。
我找到了几个算法,它们列出了图中任意给定两个节点之间的(所有)路径(例如,这样的问题: Graph Algorithm To Find All Connections Between Two Arbitrary Vertices) 对于二叉树,也存在一个算法 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()); } } }更新: 这样做的问题是,为了生成完整的句子,人们总是要追溯到词根。所以我想问题是:如何记住已经被完全访问的节点(这意味着已经浏览了所有子节点)?
推荐答案打印从根到每个叶的所有路径将意味着打印整个树,因此我只需使用简单的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)
- ...
更多推荐
深度优先搜索列出指向所有末端节点的路径
发布评论