likes
comments
collection
share

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

作者站长头像
站长
· 阅读数 19

警告：本文充满了王婆卖瓜式的宣传，但没有一句虚假宣传；

希望你了解一下 tree-lodash 的适用场景，并在合适的时候浅浅试用一下。

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

📖阅读本文，你将

  1. 了解一款 “像呼吸一样好用” 的"树操作"函数库
  2. 通过非常容易理解的动图，理解三种遍历策略
  3. 获得一个嘲笑作者的机会，以及：求求你给个 star 吧

一、不想再做 “树先生”

我抬眼看去，这前端代码歪歪扭扭，横七竖八，角落缝隙里塞满了一个熟悉的字眼：

树。

菜单是树。路由是树。DOM 是树。组织结构是树。权限点是树。低代码还是树。品类树。清单树。物料树。合约树。父节点，子节点，子子孙孙……

我翻开代码，处处是我和同事们缝缝补补的树结构操作的函数。

const newTree = oldTree.map(t => t.children.map(xxx))

不完美的实现，不完善的处理。不存在的用例。不曾出现的文档和注释。

为什么？如此常见的 “树结构”，竟然没有一款类似 lodash 的函数库？

或者有，但我竟然不知道！项目里竟然没引入！？

我躺在床上转辗反侧，横竖无法入眠，于是披衣而起，掩上门，决心要为自己，也为同事们写点什么。

于是有了一个纯纯的 “树操作” 函数开源库: tree-lodash（别名：树大师）。

它没别的本事，专注于 树结构 的操作，让你在业务中面对 树 时，操作像呼吸一样自然。

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

对，就像这么自然。

告别手写方法的“树先生”，拥抱经过考验的“树大师”。

二、tree-lodash 是个什么样的库？

2.1 简介

官网: zhangshichun.github.io/tree-lodash…

github: github.com/zhangshichu…

看名字就知道，它是一款向 lodash.js 学习的函数库，提供了一系列 “面向树” 的函数。它们当前包括：

  • foreach
  • map
  • filter
  • find
  • toArray

都是常见的函数名，看一眼都知道是做什么的那种。

2.2 用法：以 find 方法为例

如果我手头有这么一棵树：

const tree = {
  key: 1,
  children: [
    {
      key: 11,
      children: [
        {
          key: 111
        },
        {
          key: 112
        }
      ]
    },
    {
      key: 12,
      children: [
        {
          key: 122,
          children: [
            {
              key: 1221
            },
            {
              key: 1222
            }
          ]
        }
      ]
    }
  ]
}

如果我希望取到其中 key = 1221 的节点，如果没有现成可用的方法库的话，光想想就有点脑袋发涨：“难道又要花3分钟时间写个递归？”

但现在有了 tree-lodash，通过 find 方法，你可以稳定操作该结构了：

import { find } from 'tree-lodash'
const node = find(tree, (t) => t.key === 1221)
//{ key: 1221 }

就这么容易。

2.3 配置

除了最显而易见的方法之外，树大师的所有方法，还统一支持了以下配置项，让每个方法更加 灵活和强大：

type BaseOptions = {
  strategy?: 'pre' | 'post' | 'breadth',
  childrenKey?: string | number | symbol
  getChildrenKey?: Function
}

2.3.1 options.strategy：搜索策略

所有本库提供的方法都支持以下三种策略(strategy):

  • pre: 深度优先，正序搜索；
  • post：深度优先，反序搜索；
  • breadth：广度优先

只需要在 options 入参中给出相关配置即可，默认策略为 pre;

{ strategy: 'post' }

在本文第三章的动图示意里，会详细介绍搜索策略，此处不细说。

2.3.2 options.childrenKey 支持树结构子节点 key 的命名

支持传入 options.childrenKey 参数，你不仅可以用 children 表示子节点；

也可以用 subItems、babies 等所有你能想到的词语表示子节点:

{ childrenKey: 'babies' }

2.3.3 options.getChildrenKey 支持一棵树上多种 childrenKey

下面这种结构的树也是可以被解析的了：

// 注意看，这个男人叫小树，它的 childrenKey 有两种： children 和 subItems
const treeMultiChildrenKey: Tree = {
  key: '1',
  children: [
    {
      key: '2',
      subItems: [
        {
          key: '3'
        }
      ]
    },
    {
      key: '4',
      subItems: [
        {
          key: '5'
        }
      ]
    }
  ]
}

但你需要在 options.getChildrenKey 返回响应的 childrenKey:

{
  getChildrenKey: (tree, meta) => {        
    if (meta.depth === 1) {
      return 'subItems'
    }
  }
}

2.4 回调传参

在 tree-lodash 提供的方法里，大部分方法都是如下入参：

foreach(tree, predicate, [options])

其中： 第1个参数 tree: 是 一棵树 或者 一片森林。 第3个参数 options: 是上一节介绍过的配置项。

至于第二个参数，则是对树上每个节点回调的回调函数。

它通常长这样：

(treeNode, meta) => {
// treeNode 是树上的一个节点
// meta.depth 节点的深度，最顶层的节点深度为0，依次递增
// meta.parents 这是一个数组，会记录它所有的直系祖先
}

至于需不需要返回值，返回值代码什么含义，则需要根据每个方法具体判断了。

2.5 确认过单测？比写代码还累

5个方法，42个用例，几乎全覆盖的 nyc 结果：

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

三、文档里还有动图示意？太好懂了

打开 tree-lodash 的文档，你会看到一张画布和一个按钮：

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

没错，这就是 方法搜索示意图！

在本文 2.3.1 章节中提到了，每个方法都支持以下三种搜索策略：

  • pre: 深度优先，正序搜索；
  • post：深度优先，反序搜索；
  • breadth：广度优先

文本描述苍白无力，因此有了这个小小的交互式 demo,下面，我们以 foreach 方法的示意图为例，区分这三个搜索策略：

3.1 pre:深度优先，正序搜索

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

3.2 post：深度优先，反序搜索

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

3.3 breadth：广度优先

“树先生”厌倦了，开源一根【树大师】(tree-lodash)

可以明显看出，三种策略下，对树节点的遍历顺序存在显著差异，聪明的你肯定一眼就能看出来。

有同学就要发问了：

这个执行顺序有啥意义？反正都要遍历一遍的！

有意义！会直接影响结果和效率。

3.4 搜索策略影响效率

还是以 find 方法为例：

// 假设有这么一棵树
const tree = {
  key: 1,
  children: [
    {
      key: 11,
      children: [
        {
          key: 111
        },
        {
          key: 112
        }
      ]
    },
    {
      key: 12,
      children: [
        {
          key: 122,
          children: [
            {
              key: 1221
            },
            {
              key: 1222
            }
          ]
        }
      ]
    }
  ]
}

如果要在以下这棵树上找出 key === 1221 的节点，三种搜索策略分别需要多少步遍历？

pre: 7步 “树先生”厌倦了，开源一根【树大师】(tree-lodash)

post:4步 “树先生”厌倦了，开源一根【树大师】(tree-lodash)

breadth:7步 “树先生”厌倦了，开源一根【树大师】(tree-lodash)

可以看到，如果我们预期要搜索的内容来自某个叶子节点，那么执行顺序会直接导致效率上的天差地别。

3.5 搜索策略影响结果

如果我们给 find 设置的条件为 key > 11，以上三种策略返回的结果会分别是：

  • pre: 111
  • post: 111
  • breadth: 12

在树大师里，你可以在任何一个方法中选择符合自己要求的策略。

四、给个 star 吧

说了这么多，卖了这么多王婆的瓜，作者的心愿其实非常单纯：

给自己写的库浅浅的打一个广告。

如果你觉得对你有用，不妨浅浅的给作者一个 star，或者在自己的 demo 项目里安装一个试试水：

官网: zhangshichun.github.io/tree-lodash…

github: github.com/zhangshichu…

爱你哟 💗💗