关于算法:重修算法1以-On-复杂度构建树结构

已经看过一部网络小说，配角在轮回中的第九世是个大反派。而全书都是配角在致力修炼扭转第九世，算是圆满本人的修行。因为一些起因没看完，只是记得书名如同叫做《重修第九世》，然而利用收索引擎却没有找到这本书，应该是我记错了名字。不过就像这本书一样，我置信每个人都有本人没有圆满的事件，有些能够补救，而有些却无法弥补。

我在大学期间并没有把数据结构与算法学好，在步入工作的这一段时间中，多次想要去拾起算法。书倒是买了不少，视频也看过一些，但都大功告成了。于是决定通过写文章的模式来学习算法。一边通过解说的形式加深本人的了解，同时帮忙他人，另一方面也是心愿通过 flag 的模式来保质保量的学习算法嘛，先定它一个小指标，一周至多两篇对于算法的博客。

基本上，在开发任意一款 to B 利用，咱们都不可避免的波及到树形构造的增删改查。就集体而言，我接触过所有的产品中，都不可避免的树结构。集体也参考并且手写过树组件以及树操作。对树结构的计划也有肯定思考。于是，第一篇我决定就从理论业务登程，从树的构建开始：

这里为了简化，就简略设定。如果以后书节点不具备父节点，则 parentId 为 0。对于其余需要，请自行设定配置项。

interface TreeItem {
    id: number
    // 父节点的 id
    parentId: number
    // 以后树的名称
    name: string
}

事实上，在业务层面构建一棵树不算难。然而可能还是有一些算法根底不太好的小伙伴不能很快的写进去，此时咱们能够用最简略的形式。间接多层 for 循环。

function buildTree(treeItems) {
  /** 构建第一层 */  
  const treeRoots = treeItems.filter(x => x.parentId === 0)
  
  for (let first of treeRoots) {
    /** 第一层子节点 */  
    first.children = treeItems.filter(x => x.partner === first.id)
      /** 构建第二层 */
      for(let second of first.children) {// ...}
  }
}

该计划在理论业务根本不能够用，除非在理论业务中限度树的层级并且只有前几层。而且层级越大, 代码量也就越大，性能也就越差。

然而基本上所有的树操作在所有的节点中寻并插入父节点，所以该计划作为树结构的基本思路，我在此时列出以便大家能够循序渐进的思考和改良。

通过上述代码，很简略就能够发现咱们能够把以后问题合成为多个子问题。而每个子问题都是在寻找该节点的子节点，并且插入父节点的 children 中。依据这一点，咱们不难写出如下递归代码。

/** 构建树 */
const buildTree = (treeItems, id = 0) =>
  treeItems
    // 找到以后节点所有的孩子
    .filter(item => item.parentId === id)
    // 持续递归找
    .map(item => ({ ...item, children: buildTree(treeItems, item.id) }));

依据以后递归，咱们缩小了代码的冗余，并且能够“有限”的构建上来。不计算递归自身的工夫复杂度（前面有机会再说递归自身消耗的工夫复杂度）的状况下，每一次都要遍历一次数组。而数组每一个数据都要便当一次，能够得出工夫复杂度是 O(n²)。

对于大部分业务需要来说，当初能够完结了，因为在大部分业务场景中树结构自身不太会有很多的数据量。就算数据量很大的状况下，咱们也能够通过组件提早加载的形式解决。

上述计划是惯例计划，然而问题在于，性能还是低下。

性能低下的起因之一在于递归更加消耗性能而且可能会导致栈溢出谬误（js 到目前没有实现尾递归优化），这一点咱们能够利用递归转循环来做(前面再说，当初没必要)。

同时在每次构建一个节点的孩子时，都须要遍历整个数组一次，这个也是很大的损耗。事实上，优良的算法应该是能够复用后面曾经计算过的属性。

那么咱们是否可能通过一次循环解决子节点问题呢？答案也是必定的。先上代码:

function buildTreeOptimize (items) {
  // 由业务决定是否须要对 items 深拷贝一次。这里临时不做
  
  // 把每个子节点保存起来，以便前面插入父节点
  const treeDataByParentId = new Map()
  
  // 对每节点循环，找其父节点，并且放到数组中    
  items.forEach(item => {
    // map 中有父数据，插入，没有，构建并插入   
    treeDataByParentId.has(item.parentId) ? treeDataByParentId.get(item.parentId).push(item) : treeDataByParentId.set(item.parentId, [item])
  })

  // 树第一层  
  const treeRoots = []
  
  // 对每一个节点循环，找其子节点
  items.forEach(item => {
    // 子节点插入以后节点  
    item.children = (treeDataByParentId.get(item.id) || [])
    // 以后节点不具备父节点，插入第一层数组中
    if (!item.parentId) {treeRoots.push({item})
    }
  })
    
  // 返回树结构
  return treeData
}

两次 for 循环实现了树的构建？该算法工夫复杂度是 O(n)!! 能够说相当快，毕竟对于之前的代码，每个节点查问一次都要 O(n) 一次。

在第一次循环中，咱们帮忙所有的节点寻找到了父节点。即都存储到了 map 中去。在这一步中，所有的子节点依照服务端给予的数据程序顺次插入。第二次循环中，咱们间接在原 items 循环并插入第一布找到的子节点。插入节点.

其实这个算法的精妙之处在于第一步塞入 map 中的树对象和第二步塞入父节点中的树对象是是同一个对象!!!

外表上，第二步只是寻找每一个节点的子节点，但实际上在把以后节点批改的“同时”，map 中的对象节点也被改掉了，因为他们都是同一个对象(每一层的父子关系都搞定了)。所以最终仅仅只通过两次遍历便拿到对于树的数据。

大部分状况下上在业务层面做到这里就没什么太大问题了。例如 Element Tree 树形组件。以及 Ant Design 的 TreeSelect 组件。当然，同样的代码仍然适宜服务端开发。

如果你感觉这篇文章不错，心愿能够给与我一些激励，在我的 github 博客下帮忙 star 一下。

博客地址

关于算法:重修算法1以-On-复杂度构建树结构

for 循环应用

递归构建

利用对象援用构建树