JavaScript实现列表转换成树

开发树形组件时，需要树结构的数据来填充，如果此时服务器返回的是列表，那就需要我们自己来转换成树。本篇介绍了两种转换方法，供大家参考。

示例数据

var list=[
    {id: 1, name: 'child1', parentId: 0},
    {id: 2, name: 'child2', parentId: 0},
    {id: 6, name: 'child2_1', parentId: 2},
    {id: 0, name: 'root', parentId: null},
    {id: 5, name: 'child1_2', parentId: 1},
    {id: 4, name: 'child1_1', parentId: 1},
    {id: 3, name: 'child3', parentId: 0},
    {id: 7, name: 'child3_1', parentId: 3}
]

示例数据是一棵树的所有节点平铺成的列表，可以看到这棵树一共有3层，父子节点的关系通过parentId来建立。

嵌套循环法

这个方法使用了两层for循环，两层循环均遍历整个数组，在第二层循环中确定节点之间的父子关系。如果节点的parentId和另一个节点的id相等，则这两个节点是父子关系，并把子节点添加到父节点的children属性指向的数组中。这个过程跟冒泡排序类似，把所有节点之间的关系都确认了一遍
由于节点都是引用类型，只要每一个节点找到父节点，树就会自动形成，不需要额外查找孙节点，重孙乃至更深层的节点。
最后找到parentId为null的节点作为root节点，提取出来，得到我们想要的树。

function transform(list){
  var tree=[];
  for(var i=0;i<list.length;i++){
    for(var j=i;j<list.length;j++){
      if(list[j].parentId===list[i].id){
        if(list[i].children===undefined){
          list[i].children=[];
        }
        list[i].children.push(list[j]);
      }
      else if(list[j].id===list[i].parentId){
        if(list[j].children===undefined){
          list[j].children=[];
        }
        list[j].children.push(list[i]);
      }
    }
    if(list[i].parentId===null){
      tree.push(list[i]);
    }
  }
  return tree;
}

这个算法的时间复杂度是，节点数量较多时速度会比较慢。

建索引法

建索引法的核心是把父节点相同的子节点归类，并根据它们父节点的id建立索引。实际上就是建立一个字典表，父节点id作为key，子节点组成的数组作为值。

{
    "0":[
        {id: 1, name: 'child1', parentId: 0},
        {id: 2, name: 'child2', parentId: 0},
        {id: 3, name: 'child3', parentId: 0}
    ],
    "1":[
        "0": {id: 5, name: "child1_2", parentId: 1}
        "1": {id: 4, name: "child1_1", parentId: 1}
    ],
    "2":[
        {id: 2, name: 'child2', parentId: 0}
    ],
    "3":[
        {id: 7, name: 'child3_1', parentId: 3}
    ],
    "null":[
        {id: 0, name: 'root', parentId: null}
    ]
}

如果把第一个方法运行过一遍的话，就可以看出结果已经非常明显了。通过索引快速找到children数组，赋值给对应的父节点的children属性，最后返回parentId为null的节点，即为我们需要的树。
和上一个方法一样，运用到了引用类型

function transform(list){
    const group={};
    list.forEach((item)=>{
        const parentId=item.parentId;
        if(!group.hasOwnProperty(parentId)){
            group[parentId]=[];
     }
     group[parentId].push(item);
    });
    
    list.forEach(function(item){
        var id=item.id;
        if(group.hasOwnProperty(id)){
            item.children=group;
        }
    })
    
    return group["null"];
}

经过两轮循环就完成了由列表到树的转换，时间复杂度为，效率较前一种方法高出不少。