JS从扁平array转tree

发布时间:2024-08-06 10:01

有时我们需要从扁平的数组结构(flat array),根据id,和pid构建出树形数组结构(tree array),这种情形经常出现在嵌套的目录结构,如下图:

\"JS从扁平array转tree_第1张图片\"

或者企业的部门架构,也会出现上面的类似结构。
类似上面的情景,假如我们有以下的数据:
let entries = [{
    \"id\": \"12\",
    \"parentId\": \"0\",
    \"text\": \"Man\",
    \"level\": \"1\",
    \"children\": null
  },
  {
    \"id\": \"7\",
    \"parentId\": \"12\",
    \"text\": \"Other\",
    \"level\": \"2\",
    \"children\": null
  },
  {
    \"id\": \"8\",
    \"parentId\": \"7\",
    \"text\": \"Bird\",
    \"level\": \"3\",
    \"children\": null
  },
  {
    \"id\": \"9\",
    \"parentId\": \"0\",
    \"text\": \"Woman\",
    \"level\": \"1\",
    \"children\": null
  },
  {
    \"id\": \"11\",
    \"parentId\": \"9\",
    \"text\": \"Girl\",
    \"level\": \"2\",
    \"children\": null
  }
];

我们期待通过一个算法,构建出下面的结构:

[
   {
      \"id\": \"12\",
      \"parentId\": \"0\",
      \"text\": \"Man\",
      \"level\": \"1\",
      \"children\": [
         {
            \"id\": \"7\",
            \"parentId\": \"12\",
            \"text\": \"Other\",
            \"level\": \"2\",
            \"children\": [
               {
                  \"id\": \"8\",
                  \"parentId\": \"7\",
                  \"text\": \"Bird\",
                  \"level\": \"3\",
                  \"children\": []
               }
            ]
         }
      ]
   },
   {
      \"id\": \"9\",
      \"parentId\": \"0\",
      \"text\": \"Woman\",
      \"level\": \"1\",
      \"children\": [
         {
            \"id\": \"11\",
            \"parentId\": \"9\",
            \"text\": \"Girl\",
            \"level\": \"2\",
            \"children\": []
         }
      ]
   }
]

也许我们可以想到,在遍历数组的时候使用递归。没错可以解决问题,但是这种方式并不高效。

最近,在Stack Overflow上看到一个方法,感觉不错,贴出来分享一下:

function list_to_tree(list) {
    var map = {}, node, roots = [], i;
    
    for (i = 0; i < list.length; i += 1) {
      map[list[i].id] = i;      // initialize the map
      list[i].children = [];    // initialize the children
    }
    
    for (i = 0; i < list.length; i += 1) {
      node = list[i];
      if (node.parentId !== \"0\") {
        // if you have dangling branches check that map[node.parentId] exists
        list[map[node.parentId]].children.push(node);
      } else {
        roots.push(node);
      }
    }
    return roots;
}

算法的复杂度是Θ(n log(n))。

如果使用递归,那么复杂度是Θ(n^2)。如果数据集比较大,那么执行的时间会很长。

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号