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)))