扁平化与树形结构互转

扁平化数据

let arr = [
 {id: 1, name: '1', pid: 0},
 {id: 2, name: '2', pid: 1},
 {id: 3, name: '3', pid: 1},
 {id: 4, name: '4', pid: 3},
 {id: 5, name: '5', pid: 3},
]

树形数据

let tree = [
    {
        "id": 1,
        "name": "1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "3",
                "pid": 1,
                "children": [
                   {
                     "id": 4,
                     "name": "4",
                     "pid": 3,
                     "children": []
                   },
                   {
                     "id": 5,
                     "name": "5",
                     "pid": 3,
                     "children": []
                   }
                ]
            }
        ]
    }
]

树形数据->扁平化数据

1. 方法1 普通递归

function transTreeToPlain(tree) {
  let res = []
  for (const item of tree) {
    const { children, ...i } = item
    if (children && children.length) {
      res = res.concat(transTreeToPlain(children))
    }
    res.push(i)
  }
  return res
}

2. reduce实现

function transTreeToPlain(tree) {
  return tree.reduce((res, item) => {
    const { children, ...i } = item
    return res.concat(i, children && children.length ? transTreeToPlain(children) : [])
  }, [])
}

扁平化数组转tree

1. 递归

function transferPlainToTree(items) {
  let res = []
  let getChildren = (res, pid) => {
      for (const i of items) {
          if (i.pid === pid) {
              const newItem = { ...i, children: [] }
              res.push(newItem)
              getChildren(newItem.children, newItem.id)
          }
      }
  }
  getChildren(res, 0)
  return res
}
该算法的时间复杂度为O(2^n)。性能消耗很大

2. map对象实现

思路：先把数据转成Map去存储，然后再遍历的同时借助对象的引用，直接从Map找对应的数据做存储。

Object.prototype.hasOwnProperty: 方法会返回一个布尔值，指示对象自身属性中是否具有指定的属性，会忽略掉那些从原型链上继承到的属性。

function transferPlainToTree(items) {
    let res = [] // 存放结果集
    let map = {}

    // 先转成map存储
    for (const i of items) {
        map[i.id] = { ...i, children: [] }
    }

    for (const i of items) {
        const newItem = map[i.id]
        if (i.pid === 0) {
            //缓存最外层root节点
            res.push(newItem)
        } else {
            if (Object.prototype.hasOwnProperty.call(map, i.pid)) {
                map[i.pid].children.push(newItem)
            }
        }
    }
    return res
}
有两次循环，时间复杂度为O(2n)，需要一个Map把数据存储起来，空间复杂度O(n)

当然，我们也可以边做map存储，边找对应关系，一次循环搞定。

3. 收集子元素

/**
 * 扁平化处理数据
 * 思路：遍历每一个item 然后递归子项是否存在
 * @param {*} data 初始化数据
 */
function transferPlainToTree(data) {
  //首先对原数据进行深拷贝
  const _data = JSON.parse(JSON.stringify(data));
  return _data.filter((p) => {
    //每次遍历都会遍历获取子级
    const _arr = _data.filter((c) => c.pid === p.id);
    //根据_arr来判断是否有子级
    _arr.length && (p.children = _arr);
    //最后获取pid === 0的数据
    return p.pid === 0;
  });
}

4. 边做map存储，边找对应关系

思路：循环将该项的id为键，存储到map中，如果已经有该键值对了，则不用存储了，同时找该项的pid在不在map的键中，在直接对应父子关系，不在就在map中生成一个键值对，键为该pid，然后再对应父子关系。

function transferPlainToTree(items) {
    let res = [] // 存放结果集
    let map = {}
    // 判断对象是否有某个属性
    let getHasOwnProperty = (obj, property) => Object.prototype.hasOwnProperty.call(obj, property)

    // 边做map存储，边找对应关系
    for (const i of items) {
        map[i.id] = {
            ...i,
            children: getHasOwnProperty(map, i.id) ? map[i.id].children : []
        }
        const newItem = map[i.id]
        if (i.pid === 0) {
            res.push(newItem)
        } else {
            if (!getHasOwnProperty(map, i.pid)) {
                map[i.pid] = {
                    children: []
                }
            }
            map[i.pid].children.push(newItem)
        }
    }
    return res
}
一次循环就搞定了，性能也很好。时间复杂度为O(n)，需要一个Map把数据存储起来，空间复杂度O(n)