扁平数据结构转Tree
首页 > >    作者:lininn   2021年7月14日 11:38 星期三   热度:56°   百度已收录  
时间:2021-7-14 11:38   热度:56° 
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: 4},
]
时间复杂度
时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。
随着n的不断增大,时间复杂度不断增大,算法花费时间越多。 常见的时间复杂度有
常数阶O(1) 
对数阶O(log2 n) 

线性阶O(n)

线性对数阶O(n log2 n)

平方阶O(n^2)

立方阶O(n^3)

k次方阶O(n^K)

指数阶O(2^n)

计算方法

选取相对增长最高的项

不考虑性能实现,递归遍历查找

主要思路是提供一个递getChildren的方法,该方法递归去查找子集。

就这样,不用考虑性能,无脑去查,大多数人只知道递归,就是写不出来。。。

不考虑性能实现,递归遍历查找
主要思路是提供一个递getChildren的方法,该方法递归去查找子集。
就这样,不用考虑性能,无脑去查,大多数人只知道递归,就是写不出来。。。
/**
 * 递归查找,获取children
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.pid === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
}

/**
* 转换方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

复制代码
从上面的代码我们分析,该实现的时间复杂度为O(2^n)。
不用递归,也能搞定
主要思路是先把数据转成Map去存储,之后遍历的同时借助对象的引用,直接从Map找对应的数据做存储
function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
    
  // 先转成map存储
  for (const item of items) {
    itemMap[item.id] = {...item, children: []}
  }
  
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }

  }
  return result;
}

从上面的代码我们分析,一次循环就搞定了,该实现的时间复杂度为O(n),需要一个Map把数据存储起来,空间复杂度O(n)




二维码加载中...
本文作者:lininn      文章标题: 扁平数据结构转Tree
本文地址:?post=516
版权声明:若无注明,本文皆为“覆手为雨”原创,转载请保留文章出处。
分享本文至:

返回顶部    首页    手机版本    后花园   会员注册   
版权所有:覆手为雨    站长: lininn