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
}

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

一次循环

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

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, keyField = 'id', parentField = 'parent', childField = 'children') {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
}

结语

算是对树形算法的一个简单记录，这种类型的算法在项目中的使用挺多的，但是很多都是写一次就不再碰过（而且很多库都有），回顾一下防止忘记~