JS数据转换

笔试题

假设有这样一组数据，将其转换成树形结构的形式

   [{ parent: null, id: 1, name: '北京' },
    { parent: 1, id: 11, name: '朝阳' },
    { parent: 11, id: 111, name: '朝阳1号' },
    { parent: 1, id: 12, name: '海淀' },
    { parent: 12, id: 121, name: '海淀1号' },
    { parent: null, id: 2, name: '上海' },
    { parent: 2, id: 21, name: '浦东' },
    { parent: 21, id: 211, name: '浦东1号' },
    { parent: 2, id: 22, name: '虹口' },
    { parent: 22, id: 221, name: '虹口1号'}]

输出结果：

[
  {
    "parent": null,
    "id": 1,
    "name": "北京",
    "children": [
      {
        "parent": 1,
        "id": 11,
        "name": "朝阳",
        "children": [
          {
            "parent": 11,
            "id": 111,
            "name": "朝阳1号"
          }
        ]
      },
      {
        "parent": 1,
        "id": 12,
        "name": "海淀",
        "children": [
          {
            "parent": 12,
            "id": 121,
            "name": "海淀1号"
          }
        ]
      }
    ]
  },
  {
    "parent": null,
    "id": 2,
    "name": "上海",
    "children": [
      {
        "parent": 2,
        "id": 21,
        "name": "浦东",
        "children": [
          {
            "parent": 21,
            "id": 211,
            "name": "浦东1号"
          }
        ]
      },
      {
        "parent": 2,
        "id": 22,
        "name": "虹口",
        "children": [
          {
            "parent": 22,
            "id": 221,
            "name": "虹口1号"
          }
        ]
      }
    ]
  }
]

方法一

思路：在不是根节点的情况下，当前对象通过遍历每一个除自身外的所有对象进行比较，
如果其parent与数组里面的某一个item的id匹配，即说明找到其（value的）父节点

 //封装函数
function transFunc(item) {
            let tree = [],
            current;
            //遍历数组里面的每一条数据
            item.forEach((value,index)=>{
                //根据parent属性，判断是否为根节点
                if (value.parent==null) {
                    //找到根节点，保存根节点
                    tree.push(value)
                }
                //非根节点情况下，寻找它的父节点或者节点
                else{
                    /*
                    思路：在不是根节点的情况下，当前对象通过遍历每一个除自身外的所有对象进行比较，
                    如果其parent与数组里面的某一个item的id匹配，即说明找到其（value的）父节点
                     */
                    for (let i = 0; i < item.length-1; i++) {
                        //除自身以外的对象
                        if(index!==i){
                            if (item[i].id===value.parent) {
                                 //找到父节点，将当前对象赋值到current
                                 current = item[i];
                                current.children?current.children.push(value):(current.children=[value])
                            }
                        }
                    }=
                }
            })
            return tree

        }
    var items  = [{ parent: null, id: 1, name: '北京' },
    { parent: 1, id: 11, name: '朝阳' },
    { parent: 11, id: 111, name: '朝阳1号' },
    { parent: 1, id: 12, name: '海淀' },
    { parent: 12, id: 121, name: '海淀1号' },
    { parent: null, id: 2, name: '上海' },
    { parent: 2, id: 21, name: '浦东' },
    { parent: 21, id: 211, name: '浦东1号' },
    { parent: 2, id: 22, name: '虹口' },
    { parent: 22, id: 221, name: '虹口1号'}]
    console.log(JSON.stringify(transFunc(items),null,2))

写这道题时，这个方法真是让人头大，最后的current我明明没有给它添加到tree，只返回tree，但是最终结果还是能实现，惊喜又蛋疼

方法二

这个方法引用自：

JS数据转换 —— 树形结构和平铺结构的转换

  function arrToTree(arr, pid = null) {
    const res = [];
    arr.forEach(item => {
      if (item.pid === pid) {
        // 这样每次都需要遍历整个数组，因此时间复杂度为 n*n
        // const children = arrToTree(arr, item.id)

        // 往下递归时，每次数组的大小都在减小，每次都筛选掉父代元素，最终的时间复杂度为 n*logn
        const children = arrToTree(arr.filter(v => v.pid !== pid), item.id);
        if (children.length) {
          res.push({ ...item, children })
        } else {
          res.push({ ...item })
        }
      }
    });
    return res;
  }