Javascript 樹結(jié)構(gòu)數(shù)據(jù)轉(zhuǎn)換，用循環(huán)代替遞歸防止棧溢出

PrototypeZ 發(fā)布于2019-08-22 18:23 / 2164人閱讀

摘要：用循環(huán)代替遞歸防止棧溢出有些場景可能需要我們把平級的數(shù)據(jù)轉(zhuǎn)換成樹結(jié)構(gòu)，例如這樣的數(shù)據(jù)我們一般想到的就是一個遞歸就搞定，但是遞歸嵌套太多會出現(xiàn)性能問題。

用循環(huán)代替遞歸防止棧溢出

有些場景可能需要我們把平級的數(shù)據(jù)轉(zhuǎn)換成樹結(jié)構(gòu)，例如：

let data = [
    { id: 1, pid: 0 },
    { id: 2, pid: 1 },
    { id: 3, pid: 2 },
    { id: 4, pid: 3 },
    { id: 5, pid: 3 },
    { id: 6, pid: 3 },
    { id: 4, pid: 10 },
    { id: 7, pid: 10 },
    { id: 10, pid: 20 }
]

這樣的數(shù)據(jù)我們一般想到的就是一個遞歸就搞定，但是遞歸嵌套太多會出現(xiàn)性能問題。所有可以用循環(huán)來代替遞歸例如：

  function computedTree(treeData, id, pid) {
    let arr = []
    treeData.forEach((item, index) => {
        let isParent = false
        treeData.forEach(item2 => {
            if (item[pid] === item2[id]) {
                isParent = true
                !Array.isArray(item2.children) && (item2.children = [])
                item2.children.push(item)
            }
        })
        !isParent && arr.push(index)
    })
    return treeData.filter((item, index) => arr.indexOf(index) > -1)
}
let result = computedTree(data, "id", "pid")

console.log(JSON.stringify(result))

//result
[{"id": 1,"pid": 0,
    "children": [
        {"id": 2,"pid": 1,"children": [
            {"id": 3,"pid": 2,"children": [
                {"id": 4,"pid": 3}, 
                {"id": 5,"pid": 3}, 
                {"id": 6,"pid": 3}
            ]}
        ]}
    ]}, 
    {"id": 10,"pid": 20,"children": [{"id": 4,"pid": 10}, {"id": 7,"pid": 10}]
}]

這里的原理很簡單，就是利用對象的淺拷貝，把所有子父關(guān)系做一個轉(zhuǎn)換就得到結(jié)果。然后把沒有父級的做為頂級返回就得到想要的數(shù)據(jù)，若不想污染數(shù)據(jù)源可先cloneDeep后再做計算，

云服務(wù)器 GPU云服務(wù)器 js遞歸棧溢出 php遞歸獲取樹結(jié)構(gòu) 優(yōu)化遞歸數(shù)據(jù)棧 python 棧溢出

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/95803.html

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)和算法類面試題javascript代碼實(shí)現(xiàn)

摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時間刪除鏈表結(jié)點(diǎn)。寫在前面本文的題目均來自于劍指offer中的題目，題目序號保持了書中的題目序號，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會出現(xiàn)題目序號的中斷。正文面試題6：...

Dean 2019-08-22 10:39 評論0 收藏0
Javascript執(zhí)行機(jī)制--單線程，同異步任務(wù)，事件循環(huán)

摘要：如果過程中遇到引擎執(zhí)行會被掛起線程，更新保存在一個隊(duì)列中等待引擎空閑才執(zhí)行引擎線程負(fù)責(zé)解析運(yùn)行執(zhí)行時間過程會導(dǎo)致頁面渲染加載阻塞事件觸發(fā)線程，瀏覽器用以控制事件循環(huán)。序總所周知，javascript是一門依賴宿主環(huán)境的單線程的弱腳本語言，這意味著什么？ javascript的運(yùn)行環(huán)境一般都由宿主環(huán)境（如瀏覽器、Node、Ringo等）和執(zhí)行環(huán)境（Javascript引擎V8，Ja...

gaomysion 2019-08-26 10:28 評論0 收藏0
【數(shù)據(jù)科學(xué)系統(tǒng)學(xué)習(xí)】Python # 編程基礎(chǔ)[一]

摘要：在定義函數(shù)時給定的名稱稱作形參，在調(diào)用函數(shù)時你所提供給函數(shù)的值稱作實(shí)參。調(diào)用函數(shù)要調(diào)用一個函數(shù)，需要知道函數(shù)的名稱和參數(shù)。默認(rèn)參數(shù)值可以有效幫助解決這一情況。是默認(rèn)參數(shù)定義默認(rèn)參數(shù)要牢記一點(diǎn)默認(rèn)參數(shù)必須指向不變對象。關(guān)于數(shù)據(jù)科學(xué)在做什么，我們已經(jīng)在前兩篇文章中進(jìn)行了總結(jié)，即專題概述和描述性統(tǒng)計分析。要進(jìn)行數(shù)據(jù)科學(xué)的探索，需要一個好工具，就是Python。從本篇開始，將總結(jié)學(xué)習(xí)Pyth...

luckyyulin 2019-07-30 17:21 評論0 收藏0
[翻譯] JS的遞歸與TCO尾調(diào)用優(yōu)化

這兩天搜了下JS遞歸的相關(guān)文章，覺得這篇文章很不錯，就順手翻譯了下，也算給自己做個筆記，題目是我自己加的。原文很長，寫得也很詳盡，這里并非逐字翻譯，而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實(shí)際意義并不是特別大，但算法的邏輯挺有意思，不過也略抽象，理解需要花點(diǎn)時間（囧，估計我太閑了）文中的用例?全部來自原文：原文鏈接：（原題為：理解JS函數(shù)式編程中的遞歸）Underst...

pekonchan 2019-08-21 10:49 評論0 收藏0
小李飛刀：python你慢點(diǎn)飛，我的腦子還在后面追

摘要：默認(rèn)參數(shù)設(shè)置默認(rèn)參數(shù)時，有幾點(diǎn)要注意一是必選參數(shù)在前，默認(rèn)參數(shù)在后，否則的解釋器會報錯二是如何設(shè)置默認(rèn)參數(shù)。注意此處，獲得的其實(shí)是的拷貝，函數(shù)內(nèi)對的改變不會影響到。使用遞歸函數(shù)需要注意防止棧溢出。總是在最前面的叨逼叨最近總是在想成長這兩個很常常被提起的事情，這對于一個已經(jīng)25歲的半中年而言，已經(jīng)是一個不太能高頻提起的詞。但是，最近一些事情吧，總讓我覺得我的生長期似乎比正常人來的晚了...

kevin 2019-07-30 18:40 評論0 收藏0