資訊專欄INFORMATION COLUMN
摘要：前言本文研究的是如何對一個多叉樹進行全路徑的遍歷，并輸出全路徑結果。問題構建現在存在一個多叉樹，其結點情況如下圖，需要給出方法將葉子節點的所有路徑進行輸出。
多叉樹全路徑遍歷
本文為原創作品，首發于微信公眾號：【坂本先生】，如需轉載請在文首明顯位置標明“轉載于微信公眾號：【坂本先生】”，否則追究其法律責任。
前言本文研究的是如何對一個多叉樹進行全路徑的遍歷，并輸出全路徑結果。該問題的研究可以用在：Trie樹中查看所有字典值這個問題上。本文將對該問題進行詳細的模擬及進行代碼實現，討論了遞歸和非遞歸兩種方法優劣并分別進行實現，如果讀者對這兩種方法的優劣不感興趣可直接跳到問題構建章節進行閱讀。文章較長，推薦大家先收藏再進行閱讀。
文章目錄
多叉樹全路徑遍歷
前言
文章目錄
遞歸和迭代比較
遞歸
迭代
遞歸的劣勢和優勢
遞歸的劣勢
遞歸的優勢
問題構建
問題解決
遞歸方法
迭代方法
結論
參考資料
遞歸和非遞歸比較這個問題知乎上已經有了很多答案（https://www.zhihu.com/questio...），在其基礎上我進行了一波總結：
遞歸將一個問題分解為若干相對小一點的問題，遇到遞歸出口再原路返回，因此必須保存相關的中間值，這些中間值壓入棧保存，問題規模較大時會占用大量內存。
非遞歸執行效率高，運行時間只因循環次數增加而增加，沒什么額外開銷。空間上沒有什么增加
遞歸的劣勢和優勢 遞歸的劣勢遞歸容易產生"棧溢出"錯誤（stack overflow）。因為需要同時保存成千上百個調用記錄，所以遞歸非常耗費內存。
效率方面，遞歸可能存在冗余計算。使用遞歸的方式會有冗余計算（比如最典型的是斐波那契數列，計算第6個需要計算第4個和第5個，而計算第5個還需要計算第4個，所處會重復）。迭代在這方面有絕對優勢。
遞歸的優勢遞歸擁有較好的代碼可讀性，對于數據量不算太大的運算，使用遞歸算法綽綽有余。
問題構建現在存在一個多叉樹，其結點情況如下圖，需要給出方法將葉子節點的所有路徑進行輸出。
最終輸出結果應該有5個，即[rad,rac,rbe,rbf,rg]
問題解決首先我們對結點進行分析，構建一個結點類（TreeNode），然后我們需要有一個樹類（MultiTree），包含了全路徑打印的方法。最后我們需要建立一個Main方法進行測試。最終的項目結構如下：
注意：本文使用了lombok注解，省去了get，set及相關方法的實現。如果讀者沒有使用過lombok也可以自己編寫對應的get，set方法，后文會對每個類進行說明需要進行實現的方法，對核心代碼沒有影響。
TreeNode類
節點類，主要包含兩個字段：
content：用于存儲當前節點存儲的內容
childs：用于存儲子節點信息，HashMap的string存儲的是子節點內容，childs采用HashMap實現有利于實現子節點快速查找
該類中包含了必要的get，set方法，一個無參構造器，一個全參構造器
@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
private String content;
private HashMap childs;
}
MultiTree類
包含的字段只有兩個：
root：根節點
pathList：用于存儲遍歷過程中得到的路徑
該類中的構造函數中我手動創建問題構建中的樹，相關代碼如下：
public MultiTree(){
//創建根節點
HashMap rootChilds = new HashMap();
this.root = new TreeNode("r",rootChilds);
//第一層子節點
HashMap aChilds = new HashMap();
TreeNode aNode = new TreeNode("a",aChilds);
HashMap bChilds = new HashMap();
TreeNode bNode = new TreeNode("b",bChilds);
HashMap gChilds = new HashMap();
TreeNode gNode = new TreeNode("g",gChilds);
//第二層結點
HashMap dChilds = new HashMap();
TreeNode dNode = new TreeNode("d",dChilds);
HashMap cChilds = new HashMap();
TreeNode cNode = new TreeNode("c",cChilds);
HashMap eChilds = new HashMap();
TreeNode eNode = new TreeNode("e",eChilds);
HashMap fChilds = new HashMap();
TreeNode fNode = new TreeNode("f",fChilds);
//建立結點聯系
rootChilds.put("a",aNode);
rootChilds.put("b",bNode);
rootChilds.put("g",gNode);
aChilds.put("d",dNode);
aChilds.put("c",cNode);
bChilds.put("e",eNode);
bChilds.put("f",fNode);
}
在這個樹中，每個節點都有childs，如果是葉子節點，則childs中的size為0，這是下面判斷一個節點是否為葉子節點的重要依據接下來我們會對核心算法代碼進行實現。
Main類
public class Main {
public static void main(String[] args) {
MultiTree tree = new MultiTree();
List path1 = tree.listAllPathByRecursion();
System.out.println(path1);
List path2 = tree.listAllPathByNotRecursion();
System.out.println(path2);
}
}
遞歸方法
需要完善MultiTree類中的listAllPathByRecursion方法和listPath方法
遞歸過程方法：listAllPathByRecursion
算法流程圖如下：
代碼實現如下：
public void listPath(TreeNode root,String path){
if(root.getChilds().isEmpty()){//葉子節點
path = path + root.getContent();
pathList.add(path); //將結果保存在list中
return;
}else{ //非葉子節點
path = path + root.getContent() + "->";
//進行子節點的遞歸
HashMap childs = root.getChilds();
Iterator iterator = childs.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry entry = (Map.Entry)iterator.next();
TreeNode childNode = (TreeNode) entry.getValue();
listPath(childNode,path);
}
}
}
遞歸調用方法：listAllPathByRecursion
public List非遞歸方法listAllPathByRecursion(){ //清空路徑容器 this.pathList.clear(); listPath(this.root,""); return this.pathList; }
非遞歸方法的代碼量和遞歸方法一比，簡直是太多了，而且內容不好理解，不知道大家能不能看懂我寫的代碼，我已經盡力寫上相關注釋了。
首先建立了兩個棧，示意圖如下，棧的實現使用Deque，需要注意的是代碼中的空指針情況。
主棧：用于處理節點和臨時路徑的存儲，主棧為空時說明，節點處理完畢
副棧：用于存放待處理節點，副棧為空時說明，節點遍歷完畢
其他相關變量介紹：
popCount ：用于存儲一個節點的子節點的彈出個數。例如r有3個子節點，如果r對應的彈出個數為3，說明r的葉子節點處理完畢，可以彈出r。因為r彈出后，主棧沒有元素，故處理完畢。
curString：用于存儲臨時路徑，當主棧元素變化時，curString也會進行變化，例如上圖curString為“r->g->”，當棧頂元素彈出時，需要減去"g->"。如果棧頂元素是葉子節點說明該條路徑已經遍歷完成，需要添加到path路徑容器中。
程序流程圖：
具體實現代碼如下：
