算法實戰(zhàn)——多叉樹全路徑遍歷

本文為原創(chuàng)作品，首發(fā)于微信公眾號：【坂本先生】，如需轉載請在文首明顯位置標明“轉載于微信公眾號：【坂本先生】”，否則追究其法律責任。
微信文章地址：實戰(zhàn)算法——多叉樹全路徑遍歷

前言

本文研究的是如何對一個多叉樹進行全路徑的遍歷，并輸出全路徑結果。該問題的研究可以用在：Trie樹中查看所有字典值這個問題上。本文將對該問題進行詳細的模擬及進行代碼實現，討論了遞歸和非遞歸兩種方法優(yōu)劣并分別進行實現，如果讀者對這兩種方法的優(yōu)劣不感興趣可直接跳到問題構建章節(jié)進行閱讀。文章較長，推薦大家先收藏再進行閱讀。

遞歸和非遞歸比較

這個問題知乎上已經有了很多答案，https://www.zhihu.com/question/20278387
在其基礎上我進行了一波總結：

遞歸

將一個問題分解為若干相對小一點的問題，遇到遞歸出口再原路返回，因此必須保存相關的中間值，這些中間值壓入棧保存，問題規(guī)模較大時會占用大量內存。

非遞歸

執(zhí)行效率高，運行時間只因循環(huán)次數增加而增加，沒什么額外開銷?？臻g上沒有什么增加

遞歸的劣勢和優(yōu)勢

遞歸的劣勢

• 遞歸容易產生"棧溢出"錯誤（stack overflow）。因為需要同時保存成千上百個調用記錄，所以遞歸非常耗費內存。

• 效率方面，遞歸可能存在冗余計算。使用遞歸的方式會有冗余計算（比如最典型的是斐波那契數列，計算第6個需要計算第4個和第5個，而計算第5個還需要計算第4個，所處會重復）。迭代在這方面有絕對優(yōu)勢。

遞歸的優(yōu)勢

遞歸擁有較好的代碼可讀性，對于數據量不算太大的運算，使用遞歸算法綽綽有余。

問題構建

現在存在一個多叉樹，其結點情況如下圖，需要給出方法將葉子節(jié)點的所有路徑進行輸出。

最終輸出結果應該有5個，即[rad,rac,rbe,rbf,rg]

問題解決

首先我們對結點進行分析，構建一個結點類（TreeNode），然后我們需要有一個樹類（MultiTree），包含了全路徑打印的方法。最后我們需要建立一個Main方法進行測試。最終的項目結構如下：

注意：本文使用了lombok注解，省去了get，set及相關方法的實現。如果讀者沒有使用過lombok也可以自己編寫對應的get，set方法，后文會對每個類進行說明需要進行實現的方法，對核心代碼沒有影響。

TreeNode類

節(jié)點類，主要包含兩個字段：

• content：用于存儲當前節(jié)點存儲的內容
• childs：用于存儲子節(jié)點信息，HashMap的string存儲的是子節(jié)點內容，childs采用HashMap實現有利于實現子節(jié)點快速查找

該類中包含了必要的get，set方法，一個無參構造器，一個全參構造器

@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
    private String content;
    private HashMap<String,TreeNode> childs;
}

MultiTree類

包含的字段只有兩個：

• root：根節(jié)點
• pathList：用于存儲遍歷過程中得到的路徑

該類中的構造函數中我手動創(chuàng)建問題構建中的樹，相關代碼如下：

    public MultiTree(){
        //創(chuàng)建根節(jié)點
        HashMap rootChilds = new HashMap();
        this.root = new TreeNode("r",rootChilds);

        //第一層子節(jié)點
        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);
    }

在這個樹中，每個節(jié)點都有childs，如果是葉子節(jié)點，則childs中的size為0，這是下面判斷一個節(jié)點是否為葉子節(jié)點的重要依據接下來我們會對核心算法代碼進行實現。

Main類

public class Main {
    public static void main(String[] args) {
        MultiTree tree = new MultiTree();
        List<String> path2 = tree.listAllPathByRecursion();
        System.out.println(path2);
        List<String> path3 = tree.listAllPathByNotRecursion();
        System.out.println(path3);
    }
}

遞歸方法

需要完善MultiTree類中的listAllPathByRecursion方法和listPath方法

遞歸過程方法：listAllPathByRecursion

算法流程圖如下：

代碼實現如下：

public void listPath(TreeNode root,String path){

    if(root.getChilds().isEmpty()){//葉子節(jié)點
        path = path + root.getContent();
        pathList.add(path); //將結果保存在list中
        return;
    }else{ //非葉子節(jié)點
        path = path  + root.getContent() + "->";

        //進行子節(jié)點的遞歸
        HashMap<String, TreeNode> 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<String> listAllPathByRecursion(){
    //清空路徑容器
    this.pathList.clear();
    listPath(this.root,"");
    return this.pathList;
}

非遞歸方法

非遞歸方法的代碼量和遞歸方法一比，簡直是太多了，而且內容不好理解，不知道大家能不能看懂我寫的代碼，我已經盡力寫上相關注釋了。

首先建立了兩個棧，示意圖如下，棧的實現使用Deque，需要注意的是代碼中的空指針情況。

• 主棧：用于處理節(jié)點和臨時路徑的存儲，主棧為空時說明，節(jié)點處理完畢

• 副棧：用于存放待處理節(jié)點，副棧為空時說明，節(jié)點遍歷完畢

  

其他相關變量介紹：

• popCount ：用于存儲一個節(jié)點的子節(jié)點的彈出個數。例如r有3個子節(jié)點，如果r對應的彈出個數為3，說明r的葉子節(jié)點處理完畢，可以彈出r。因為r彈出后，主棧沒有元素，故處理完畢。
• curString：用于存儲臨時路徑，當主棧元素變化時，curString也會進行變化，例如上圖curString為“r->g->”，當棧頂元素彈出時，需要減去"g->"。如果棧頂元素是葉子節(jié)點說明該條路徑已經遍歷完成，需要添加到path路徑容器中。

程序流程圖：

具體實現代碼如下：

/**
 * 非遞歸方法輸出所有路徑
 */
public List<String> listAllPathByNotRecursion(){
    //清空路徑容器
    this.pathList.clear();
    //主棧，用于計算處理路徑
    Deque<TreeNode> majorStack = new ArrayDeque();
    //副棧，用于存儲待處理節(jié)點
    Deque<TreeNode> minorStack = new ArrayDeque();
    minorStack.addLast(this.root);

    HashMap<String,Integer> popCount = new HashMap<>();
    String curString  = "";

    while(!minorStack.isEmpty()){
        //出副棧，入主棧
        TreeNode minLast = minorStack.pollLast();
        majorStack.addLast(minLast);
        curString+=minLast.getContent()+"->";
        //將該節(jié)點的子節(jié)點入副棧
        if(!minLast.getChilds().isEmpty()){
            HashMap<String, TreeNode> childs = minLast.getChilds();
            Iterator iterator = childs.entrySet().iterator();
            while(iterator.hasNext()){
                Map.Entry entry = (Map.Entry)iterator.next();
                TreeNode childNode  = (TreeNode) entry.getValue();
                minorStack.addLast(childNode);
            }
        }
        //出主棧
        TreeNode majLast = majorStack.peekLast();
        //循環(huán)條件：棧頂為葉子節(jié)點 或 棧頂節(jié)點孩子節(jié)點遍歷完了（需要注意空指針問題）
        while(majLast.getChilds().size() ==0 ||
                (popCount.get(majLast.getContent())!=null && popCount.get(majLast.getContent()).equals(majLast.getChilds().size()))){

            TreeNode last = majorStack.pollLast();
            majLast = majorStack.peekLast();

            if(majLast == null){ //此時主棧為空，運算完畢
                return this.pathList;
            }
            if(popCount.get(majLast.getContent())==null){//第一次彈出孩子節(jié)點，彈出次數設為1
                popCount.put(majLast.getContent(),1);
            }else{ //非第一次彈出孩子節(jié)點，在原有基礎上加1
                popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
            }
            String lastContent = last.getContent();
            if(last.getChilds().isEmpty()){//如果是葉子節(jié)點才將結果加入路徑集中
                this.pathList.add(curString.substring(0,curString.length()-2));
            }
            //調整當前curString，減去2是減的“->”這個符號
            curString = curString.substring(0,curString.length()-lastContent.length()-2);
        }
    }
    return this.pathList;
}

測試

調用Main類中的main方法，得到執(zhí)行結果，和預期結果相同，代碼通過測試

listAllPathByRecursion[r->a->c, r->a->d, r->b->e, r->b->f, r->g]
listAllPathByNotRecursion[r->g, r->b->f, r->b->e, r->a->d, r->a->c]

結論

其實該文章是我在研究《基于Trie樹的敏感詞過濾算法實現》的一個中間產物，其實原來應該也實現過多叉樹的路徑遍歷問題，但是因為時間原因加之原來沒有較好的知識管理系統，代碼和筆記都丟了，今天趁機再進行一波總結。希望該文章能夠幫助到需要的人。

參考資料

• [遞歸」和「迭代」有哪些區(qū)別？ - 葉世清的回答 - 知乎
• 遞歸如何轉換為非遞歸