国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

多叉樹全路徑遍歷

MartinHan / 1028人閱讀

摘要:前言本文研究的是如何對一個(gè)多叉樹進(jìn)行全路徑的遍歷,并輸出全路徑結(jié)果。問題構(gòu)建現(xiàn)在存在一個(gè)多叉樹,其結(jié)點(diǎn)情況如下圖,需要給出方法將葉子節(jié)點(diǎn)的所有路徑進(jìn)行輸出。

多叉樹全路徑遍歷

本文為原創(chuàng)作品,首發(fā)于微信公眾號:【坂本先生】,如需轉(zhuǎn)載請?jiān)谖氖酌黠@位置標(biāo)明“轉(zhuǎn)載于微信公眾號:【坂本先生】”,否則追究其法律責(zé)任。

前言

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

文章目錄

多叉樹全路徑遍歷

前言

文章目錄

遞歸和迭代比較

遞歸

迭代

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

遞歸的劣勢

遞歸的優(yōu)勢

問題構(gòu)建

問題解決

遞歸方法

迭代方法

結(jié)論

參考資料

遞歸和非遞歸比較

這個(gè)問題知乎上已經(jīng)有了很多答案(https://www.zhihu.com/questio...),在其基礎(chǔ)上我進(jìn)行了一波總結(jié):

遞歸

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

非遞歸

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

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

遞歸容易產(chǎn)生"棧溢出"錯(cuò)誤(stack overflow)。因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用記錄,所以遞歸非常耗費(fèi)內(nèi)存。

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

遞歸的優(yōu)勢

遞歸擁有較好的代碼可讀性,對于數(shù)據(jù)量不算太大的運(yùn)算,使用遞歸算法綽綽有余。

問題構(gòu)建

現(xiàn)在存在一個(gè)多叉樹,其結(jié)點(diǎn)情況如下圖,需要給出方法將葉子節(jié)點(diǎn)的所有路徑進(jìn)行輸出。

最終輸出結(jié)果應(yīng)該有5個(gè),即[rad,rac,rbe,rbf,rg]

問題解決

首先我們對結(jié)點(diǎn)進(jìn)行分析,構(gòu)建一個(gè)結(jié)點(diǎn)類(TreeNode),然后我們需要有一個(gè)樹類(MultiTree),包含了全路徑打印的方法。最后我們需要建立一個(gè)Main方法進(jìn)行測試。最終的項(xiàng)目結(jié)構(gòu)如下:

注意:本文使用了lombok注解,省去了get,set及相關(guān)方法的實(shí)現(xiàn)。如果讀者沒有使用過lombok也可以自己編寫對應(yīng)的get,set方法,后文會對每個(gè)類進(jìn)行說明需要進(jìn)行實(shí)現(xiàn)的方法,對核心代碼沒有影響。

TreeNode類

節(jié)點(diǎn)類,主要包含兩個(gè)字段:

content:用于存儲當(dāng)前節(jié)點(diǎn)存儲的內(nèi)容

childs:用于存儲子節(jié)點(diǎn)信息,HashMap的string存儲的是子節(jié)點(diǎn)內(nèi)容,childs采用HashMap實(shí)現(xiàn)有利于實(shí)現(xiàn)子節(jié)點(diǎn)快速查找

該類中包含了必要的get,set方法,一個(gè)無參構(gòu)造器,一個(gè)全參構(gòu)造器

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

MultiTree類

包含的字段只有兩個(gè):

root:根節(jié)點(diǎn)

pathList:用于存儲遍歷過程中得到的路徑

該類中的構(gòu)造函數(shù)中我手動創(chuàng)建問題構(gòu)建中的樹,相關(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è)樹中,每個(gè)節(jié)點(diǎn)都有childs,如果是葉子節(jié)點(diǎn),則childs中的size為0,這是下面判斷一個(gè)節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)的重要依據(jù)接下來我們會對核心算法代碼進(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方法

遞歸過程方法: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;
}
非遞歸方法

非遞歸方法的代碼量和遞歸方法一比,簡直是太多了,而且內(nèi)容不好理解,不知道大家能不能看懂我寫的代碼,我已經(jīng)盡力寫上相關(guān)注釋了。

首先建立了兩個(gè)棧,示意圖如下,棧的實(shí)現(xiàn)使用Deque,需要注意的是代碼中的空指針情況。

主棧:用于處理節(jié)點(diǎn)和臨時(shí)路徑的存儲,主棧為空時(shí)說明,節(jié)點(diǎn)處理完畢

副棧:用于存放待處理節(jié)點(diǎn),副棧為空時(shí)說明,節(jié)點(diǎn)遍歷完畢

其他相關(guān)變量介紹:

popCount :用于存儲一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的彈出個(gè)數(shù)。例如r有3個(gè)子節(jié)點(diǎn),如果r對應(yīng)的彈出個(gè)數(shù)為3,說明r的葉子節(jié)點(diǎn)處理完畢,可以彈出r。因?yàn)閞彈出后,主棧沒有元素,故處理完畢。

curString:用于存儲臨時(shí)路徑,當(dāng)主棧元素變化時(shí),curString也會進(jìn)行變化,例如上圖curString為“r->g->”,當(dāng)棧頂元素彈出時(shí),需要減去"g->"。如果棧頂元素是葉子節(jié)點(diǎn)說明該條路徑已經(jīng)遍歷完成,需要添加到path路徑容器中。

程序流程圖:

具體實(shí)現(xiàn)代碼如下:

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

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

    while(!minorStack.isEmpty()){
        //出副棧,入主棧
        TreeNode minLast = minorStack.pollLast();
        majorStack.addLast(minLast);
        curString+=minLast.getContent()+"->";
        //將該節(jié)點(diǎn)的子節(jié)點(diǎn)入副棧
        if(!minLast.getChilds().isEmpty()){
            HashMap 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é)點(diǎn) 或 棧頂節(jié)點(diǎn)孩子節(jié)點(diǎn)遍歷完了(需要注意空指針問題)
        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){ //此時(shí)主棧為空,運(yùn)算完畢
                return this.pathList;
            }
            if(popCount.get(majLast.getContent())==null){//第一次彈出孩子節(jié)點(diǎn),彈出次數(shù)設(shè)為1
                popCount.put(majLast.getContent(),1);
            }else{ //非第一次彈出孩子節(jié)點(diǎn),在原有基礎(chǔ)上加1
                popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
            }
            String lastContent = last.getContent();
            if(last.getChilds().isEmpty()){//如果是葉子節(jié)點(diǎn)才將結(jié)果加入路徑集中
                this.pathList.add(curString.substring(0,curString.length()-2));
            }
            //調(diào)整當(dāng)前curString,減去2是減的“->”這個(gè)符號
            curString = curString.substring(0,curString.length()-lastContent.length()-2);
        }
    }
    return this.pathList;
}
測試

調(diào)用Main類中的main方法,得到執(zhí)行結(jié)果,和預(yù)期結(jié)果相同,代碼通過測試

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]
結(jié)論

其實(shí)該文章是我在研究《基于Trie樹的敏感詞過濾算法實(shí)現(xiàn)》的一個(gè)中間產(chǎn)物,其實(shí)原來應(yīng)該也實(shí)現(xiàn)過多叉樹的路徑遍歷問題,但是因?yàn)闀r(shí)間原因加之原來沒有較好的知識管理系統(tǒng),代碼和筆記都丟了,今天趁機(jī)再進(jìn)行一波總結(jié)。希望該文章能夠幫助到需要的人。

參考資料

[遞歸」和「迭代」有哪些區(qū)別? - 葉世清的回答 - 知乎

遞歸如何轉(zhuǎn)換為非遞歸

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/74672.html

相關(guān)文章

  • js遍歷叉樹叉樹結(jié)構(gòu)

    摘要:二叉樹的層級遍歷創(chuàng)建一個(gè)二叉樹輸出函數(shù)先訪問左子樹,再訪問自身,再訪問右子樹先訪問自身,再訪問左子樹,再訪問右子樹先訪問左子樹,再訪問右子樹再訪問自身層級遍歷多叉樹的層級遍歷創(chuàng)建一個(gè)多叉樹輸出函數(shù)遞歸遍歷每個(gè)節(jié)點(diǎn)方法方法方法層級遍歷每 1、二叉樹的層級遍歷 創(chuàng)建一個(gè)二叉樹 class Binary{ constructor(data,left,right){ this.data...

    junbaor 評論0 收藏0
  • 遍歷叉樹(遞歸、非遞歸廣度優(yōu)先、深度優(yōu)先)

    簡單的遍歷一個(gè)樹形結(jié)構(gòu)數(shù)據(jù)的幾種方法、非遞歸方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...

    wing324 評論0 收藏0
  • 面試題:給你個(gè)id,去拿到name,叉樹遍歷

    前天面試遇到一個(gè)多叉樹面試的題目,在這里分享記錄一下。 題目:一個(gè)樹形的數(shù)據(jù)(如下數(shù)據(jù)),面試官給你一個(gè)id,然后拿到對應(yīng)的name? 數(shù)據(jù)結(jié)構(gòu)大概是這個(gè)樣子 var cityData = [ { id: 1, name: 廣東省, children: [ { id: 11, ...

    jayce 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<