js将扁平结构数据转换为树形结构

概述

最近项目又频繁须要对扁平结构进行树形转换,这个算法从我最先接触的时候使用了递归,到如今的单次循环完成,简单记录一下算法的演变

递归实现

function transformTree (list) {
    const tree = []
    
    for (let i = 0, len = list.length; i < len; i++) {
        if (!list[i].pid) {
            const item = queryChildren(list[i], list)
            
            tree.push(item)
        }
    }
    
    return tree
}

function queryChildren (parent, list) {
    const children = []
    
    for (let i = 0, len = list.length; i < len; i++) {
        if (list[i].pid === parent.id) {
            const item = queryChildren(list[i], list)

            children.push(item)
        }
    }
    
    if (children.length) {
        parent.children = children
    }
    
    return parent
}

尽管后续对上面的算法进行了不少优化,可是仍未离开递归,递归可能遇到的问题仍是会有可能遇到算法

循环实现

随着进化,循环代替递归是必然的结果~数组

两次循环

开始使用循环实现时,使用了两次循环完成转换,先进行一次循环将数据转换成 map 结构,使其能经过 id 快速查询优化

function transformTree (list) {
    const tree = []
    const record = {}
    const length = list.length
    
    for (let i = 0; i < length; i++) {
        const item = list[i]
        
        item.children = [] // 重置 children
        record[item.id] = item
    }
    
    for (let i = 0; i < length; i++) {
        const item = list[i]
        
        if (item.pid) {
            if (record[item.pid]) {
                record[item.pid].children.push(item)
            }
        } else {
            tree.push(item)
        }
    }
    
    return tree
}

上面的算法相较于递归的实现,不存在栈溢出的问题,并且是线性复杂度,效率已经提升了许多code

一次循环

再进行必定的优化,最后变成一次循环完成树形构建orm

function transformTree (list) {
    const tree = []
    const record = {}
    
    for (let i = 0, len = list.length; i < len; i++) {
        const item = list[i]
        const id = item.id
        
        if (record[id]) {
            item.children = record[id]
        } else {
            item.children = record[id] = []
        }
        
        if (item.pid) {
            if (!record[item.pid]) {
                record[item.pid] = []
            }
            
            record[item.pid].push(item)
        } else {
            tree.push(item)
        }
    }
}

使用对象变量的特性,使用 map 结构直接指向 children 数组,在循环中初始化的同时还能快速查找插入相应的 children 里,使其在一次循环内完成构建,最后附上完整版~对象

function transformTree (list, options = {}) {
    const {
        keyField = 'id',
        childField = 'children',
        parentField = 'parent'
    } = options

    const tree = []
    const record = {}

    for (let i = 0, len = list.length; i < len; i++) {
        const item = list[i]
        const id = item[keyField]

        if (!id) {
            continue
        }

        if (record[id]) {
            item[childField] = record[id]
        } else {
            item[childField] = record[id] = []
        }

        if (item[parentField]) {
            const parentId = item[parentField]

            if (!record[parentId]) {
                record[parentId] = []
            }

            record[parentId].push(item)
        } else {
            tree.push(item)
        }
    }

    return tree
}

结语

算是对树形算法的一个简单记录,这种类型的算法在项目中的使用挺多的,可是不少都是写一次就再也不碰过(并且不少库都有),回顾一下防止忘记~递归

相关文章
相关标签/搜索