javascript生成一棵树

问题描述

输入一串父子节点对的数组，利用其构造一颗树

输入

const arr = [
    {id:1,parentid:null},
    {id:2,parentid:1},
    {id:3,parentid:1},
    {id:4,parentid:2},
    {id:5,parentid:3}
]

解决思路

1. 明确输出的形式：

   type1: {id:0,chid:[{id,child},{id,child},{id,child}]}

   type2: 0:{1:{5:{}},2:{},3:{},4:{}}

   实践中type1更为实用，故选择之

2. 每次只能处理一对父子关系，树形结构的核心是节点，也即处理两个节点。

   由于每个节点的状态是需要维护的，因此需要用一种结构存储每个节点并更新之，最后程序只需要找到根节点是谁即可输出完整的属性结构；

解决代码

const arr = [
    {id:1,parentid:null},
    {id:2,parentid:1},
    {id:3,parentid:1},
    {id:4,parentid:2},
    {id:5,parentid:3}
]

function generateTree(srcList){
    // 1. 明确输出的形式：
    // type1:{id:0,chid:[{id,child},{id,child},{id,child}]}
    // type2: 0:{1:{5:{}},2:{},3:{},4:{}}
    // 实践中type1更为实用，故选择之
    // 2. 每次只能处理一对父子关系，树形结构的核心是节点，也即处理两个节点。
    // 由于每个节点的状态是需要维护的，因此需要用一种结构存储每个节点并更新之，最后程序只需要找到根节点是谁即可输出完整的属性结构；
    let nodeRigister = {}
    let root = undefined
    srcList.forEach(element => {
        let childId = element.id
        let parentId = element.parentid
        // parentId可能引入新的信息：判断是否为根节点。需要特判之
        if(!parentId){
            root = childId
        } 
        // 处理儿子节点
        if(!(childId in Object.keys(nodeRigister))){
            nodeRigister[childId] = {id:childId,child:[]}
        }
        // 处理父节点
        if(parentId && parentId in Object.keys(nodeRigister)){
            nodeRigister[parentId].child.push(nodeRigister[childId])
        }else if(parentId){
            nodeRigister[parentId] = {id:parentId,child:[nodeRigister[childId]]}
        }
    });
    return nodeRigister[root]
}

console.log(JSON.stringify(generateTree(arr)))