快捷導(dǎo)航

JavaScript遞歸構(gòu)建樹形結(jié)構(gòu)的兩種方法

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

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

原始數(shù)據(jù)結(jié)構(gòu)

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

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

代碼實(shí)現(xiàn)

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

執(zhí)行過程解析

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

時(shí)間復(fù)雜度分析

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

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

代碼實(shí)現(xiàn)

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

執(zhí)行過程解析

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

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

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

時(shí)間復(fù)雜度分析

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

兩種方法對(duì)比

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

實(shí)際應(yīng)用建議

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

擴(kuò)展功能

可以在基礎(chǔ)實(shí)現(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é)點(diǎn)過濾
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;
}

理解這些實(shí)現(xiàn)原理后，你可以根據(jù)具體業(yè)務(wù)需求靈活調(diào)整樹形結(jié)構(gòu)的構(gòu)建方式。

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

您可能感興趣的文章: