Javascript 樹結構數據轉換，用循環代替遞歸防止棧溢出

PrototypeZ 發布于2019-08-22 18:23 / 2143人閱讀

摘要：用循環代替遞歸防止棧溢出有些場景可能需要我們把平級的數據轉換成樹結構，例如這樣的數據我們一般想到的就是一個遞歸就搞定，但是遞歸嵌套太多會出現性能問題。

用循環代替遞歸防止棧溢出

有些場景可能需要我們把平級的數據轉換成樹結構，例如：

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 }
]

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

  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}]
}]

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

GPU云服務器云服務器 js遞歸棧溢出 php遞歸獲取樹結構優化遞歸數據棧 python 棧溢出

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/95803.html

數據結構和算法類面試題javascript代碼實現

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

Dean 2019-08-22 10:39 評論0 收藏0
Javascript執行機制--單線程，同異步任務，事件循環

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

gaomysion 2019-08-26 10:28 評論0 收藏0
【數據科學系統學習】Python # 編程基礎[一]

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

luckyyulin 2019-07-30 17:21 評論0 收藏0
[翻譯] JS的遞歸與TCO尾調用優化

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

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

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

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