乐趣区

关于递归:JS从扁平array转tree

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

或者企业的部门架构,也会呈现下面的相似构造。

相似下面的情景,如果咱们有以下的数据:

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)。如果数据集比拟大,那么执行的工夫会很长。

退出移动版