JavaScript遞歸構建樹形結構的兩種方法

更新時間：2025年09月01日 15:17:53 作者：郭澤元

本文給大家詳細講解如何使用純JavaScript遞歸方法將扁平數據轉換為樹形結構,并解釋兩種實現(xiàn)方式的原理和區(qū)別,感興趣的朋友一起看看吧

原始數據結構

let data = [
    {name: '一級', id: 12, pid: 0},    // pid=0 表示根節(jié)點
    {name: '二級', id: 32, pid: 0},    // pid=0 表示根節(jié)點
    {name: '一級-1', id: 23, pid: 12}, // pid=12 表示父節(jié)點是id=12的節(jié)點
    {name: '二級-1', id: 34, pid: 32}, // pid=32 表示父節(jié)點是id=32的節(jié)點
];

方法一：遞歸實現(xiàn)詳解

代碼實現(xiàn)

function buildTree(items, parentId = 0) {
    let result = [];
    // 1. 找出所有父節(jié)點為parentId的項
    let children = items.filter(item => item.pid === parentId);
    // 2. 遞歸處理每個子項
    children.forEach(child => {
        // 3. 查找當前項的子項
        let childNodes = buildTree(items, child.id);
        // 4. 如果有子項，則添加到children屬性中
        if (childNodes.length > 0) {
            child.children = childNodes;
        }
        result.push(child);
    });
    return result;
}
let treeData = buildTree(data);

執(zhí)行過程解析

初始調用：buildTree(data, 0)
parentId = 0，查找所有pid=0的項 → [{一級}, {二級}]
對每個根節(jié)點進行處理：
處理{一級}：
遞歸調用buildTree(data, 12)
查找pid=12的項 → [{一級-1}]
處理{一級-1}：
遞歸調用buildTree(data, 23)
查找pid=23的項 → []（空數組）
無子節(jié)點，直接返回[{一級-1}]
將子節(jié)點數組賦值給{一級}.children
處理{二級}：
類似過程，最終{二級}.children = [{二級-1}]
遞歸終止條件：當某個節(jié)點沒有子節(jié)點時，遞歸自然終止

時間復雜度分析

每次遞歸調用都需要遍歷整個數組查找子節(jié)點
最壞情況下時間復雜度為O(n²)，n為節(jié)點數量
適合小型數據集

方法二：優(yōu)化實現(xiàn)詳解（非遞歸）

代碼實現(xiàn)

function buildTreeOptimized(items) {
    let map = {};  // 存儲id到節(jié)點的映射
    let result = [];  // 最終結果
    // 1. 構建映射表
    items.forEach(item => {
        map[item.id] = {...item, children: []};
    });
    // 2. 構建樹形結構
    items.forEach(item => {
        let node = map[item.id];
        if (item.pid === 0) {
            // 根節(jié)點
            result.push(node);
        } else {
            // 子節(jié)點
            if (map[item.pid]) {
                map[item.pid].children.push(node);
            }
        }
    });
    return result;
}
let optimizedTree = buildTreeOptimized(data);

執(zhí)行過程解析

構建映射表：
- 遍歷所有節(jié)點，創(chuàng)建以id為鍵的映射表
- 每個節(jié)點添加空的children數組
- 映射表示例：

{
    12: {name: '一級', id:12, pid:0, children: []},
    32: {name: '二級', id:32, pid:0, children: []},
    23: {name: '一級-1', id:23, pid:12, children: []},
    34: {name: '二級-1', id:34, pid:32, children: []}
}

構建樹形結構：
- 再次遍歷所有節(jié)點：
- 如果pid=0，直接加入結果數組
- 否則，找到父節(jié)點(map[pid])，將當前節(jié)點加入父節(jié)點的children數組
- 通過引用關系，所有節(jié)點的父子關系自動建立

時間復雜度分析

只需要兩次遍歷：O(n)時間復雜度
利用JavaScript對象引用的特性，效率更高
適合大型數據集

兩種方法對比

特性	遞歸方法	優(yōu)化方法
實現(xiàn)方式	遞歸	循環(huán)+對象引用
時間復雜度	O(n²)	O(n)
空間復雜度	O(n) (調用棧)	O(n) (映射表)
適用場景	小型數據集	大型數據集
代碼可讀性	較高	中等
最大遞歸深度限制	可能受限	無限制

實際應用建議

小型數據集（<1000節(jié)點）：兩種方法都可以，遞歸方法代碼更簡潔
大型數據集：務必使用優(yōu)化方法，避免遞歸深度問題和性能瓶頸
極端大數據：考慮分批次處理或使用Web Worker

擴展功能

可以在基礎實現(xiàn)上添加以下功能：

// 添加排序功能
function buildTree(items, parentId = 0, sortKey = 'id') {
    let result = [];
    let children = items.filter(item => item.pid === parentId);
    // 排序
    children.sort((a, b) => a[sortKey] - b[sortKey]);
    children.forEach(child => {
        let childNodes = buildTree(items, child.id, sortKey);
        if (childNodes.length > 0) {
            child.children = childNodes;
        }
        result.push(child);
    });
    return result;
}
// 添加節(jié)點過濾
function buildTreeWithFilter(items, parentId = 0, filterFn = () => true) {
    let result = [];
    let children = items.filter(item => item.pid === parentId && filterFn(item));
    children.forEach(child => {
        let childNodes = buildTreeWithFilter(items, child.id, filterFn);
        if (childNodes.length > 0) {
            child.children = childNodes;
        }
        result.push(child);
    });
    return result;
}

理解這些實現(xiàn)原理后，你可以根據具體業(yè)務需求靈活調整樹形結構的構建方式。

到此這篇關于JavaScript 遞歸構建樹形結構詳解的文章就介紹到這了,更多相關js遞歸樹形結構內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: