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