本文介紹了深度優(yōu)先搜索列出指向所有末端節(jié)點的路徑的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！
問題描述
您好，我有一棵樹，我想在其中獲取從初始(根)節(jié)點到所有葉子的路徑。
我找到了幾個算法，它們列出了圖中任意給定兩個節(jié)點之間的(所有)路徑(例如，這樣的問題：
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices)
對于二叉樹，也存在一個算法
http://techieme.in/print-all-paths-in-a-tree/
但我在一棵有各種分枝因素的樹上工作。
有沒有更好的方法來實現(xiàn)我想要做的事情，而不是遍歷一次樹以獲得所有樹葉，然后結合初始節(jié)點對所有樹葉運行上述算法？
我在考慮實現(xiàn)簡單的DFS，通過一些額外的堆棧來擴展，這些堆棧包含沿著路徑到單個葉的所有節(jié)點，然后通過循環(huán)遍歷這些堆棧列出所有句子。
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());
}
}
}
更新：
這樣做的問題是，為了生成完整的句子，人們總是要追溯到詞根。所以我想問題是：如何記住已經(jīng)被完全訪問的節(jié)點(這意味著已經(jīng)瀏覽了所有子節(jié)點)？
推薦答案
打印從根到每個葉的所有路徑將意味著打印整個樹，因此我只需使用簡單的DFS并為每個節(jié)點執(zhí)行以下操作：
將其添加到列表/堆棧
如果節(jié)點有子節(jié)點，則對子節(jié)點重復此操作
如果節(jié)點是葉，則打印列表/堆棧
從列表/堆棧中彈出節(jié)點
示例：
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)
…
這篇關于深度優(yōu)先搜索列出指向所有末端節(jié)點的路徑的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
