JavaScript 处理树结构数据

本文最后更新于:2021年6月21日 晚上

场景

前端项目中,有一些需要处理树结构数据的情况,(一年)之前吾辈曾经写过一篇文章,但现在,吾辈有了更好的解决方案。

思考

之前吾辈使用 Proxy 的方式抹平树结构数据的差异,然后再处理。后来吾辈发现这完全是多此一举,在使用过 antd 的 Tree 组件deepdash 之后,确实第一步是完全没有必要的。

以下代码均由 TypeScript 实现,最好能了解 TypeScript 类型操作

其实树结构数据可以抽象出非常简单的 interface(接口)

interface Node {
  id: string;
  children: Node[];
}

无非是业务中多了一些字段,这两个字段的名字有所不同罢了。

例如系统菜单与系统权限

interface SysMenu {
  id: number; // 菜单 id
  name: string; // 显示的名称
  sub: SysMenu[]; // 子级菜单
}

interface SysPermission {
  uid: string; // 系统唯一 uuid
  label: string; // 显示的菜单名
  children: SysPermission[]; // 子权限
}

可以看到,它们都有 idchildren 字段,只是名字不同。那么,根据封装不变的部分,将变化的部分交予外部输入的封装原则,这两个字段便由外部指定了。

操作

那么,树结构都有哪些操作呢?

  • reduce 归并
  • each 遍历
  • map 映射
  • filter 过滤
  • treeToList 树转换为列表
  • listToTree 列表转换为树

然而,吾辈目前用到的仅有 each/map/filter/treeToList,所以先行实现下面几个。

定义通用树结构需要的必须参数类型

如果树结构必须包含 id/children,那么,便可以以此定义树结构操作的通用参数了。

export interface TreeOption<T extends object> {
  /**
   * 唯一标识的字段
   */
  id: keyof T;
  /**
   * 子节点的字段
   */
  children: keyof T;
}

上面是一个接口,必须声明 id/children 的字段名是什么,便于内部实现读取树节点信息。

感谢 TypeScript,没有它就无法定义出类型,就不能检查出代码中的细微错误。例如,Java 就很难定义反射相关的类型,通常只能使用 String

treeMap

下面实现 treeMap,其实就是一个递归函数。

import { TreeOption } from "./treeOption";

/**
 * 树结构映射
 * 使用深度优先算法
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeMap<
  T extends object,
  C extends TreeOption<T>,
  F extends (
    t: Omit<T, C["children"]> & Record<C["children"], ReturnType<F>[]>,
    path: T[C["id"]][]
  ) => object
>(nodeList: T[], fn: F, options: C): ReturnType<F>[] {
  function inner(nodeList: T[], parentPath: T[C["id"]][]): any {
    return nodeList.map((node) => {
      const path = [...parentPath, node[options.id]];
      const children = node[options.children] as any as T[];
      if (!children) {
        return fn(node as any, path);
      }
      return fn(
        {
          ...node,
          [options.children]: inner(children, path),
        },
        path
      );
    });
  }

  return inner(nodeList, []);
}

不过细心的人可能已经发现,这里做了两个奇怪的操作

  1. 先处理了所有子节点,然后将处理后子节点传入到 map 函数中,而非反过来。– 这其实是为了兼容前端框架 react 的 JSX。
  2. 计算了节点的 path,并丢到 map 函数中。– 这是为了能轻松知道当前节点的所有父节点以及层级,便于在有需要时(例如转换为列表)能拿到这个关键信息。

treeFilter

嗯,下面的函数都将基于 treeMap 实现了(#笑)

import { TreeOption } from "./treeOption";
import { treeMap } from "./treeMap";

/**
 * 过滤一个树节点列表
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeFilter<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C["id"]][]) => boolean,
  options: C
): T[] {
  return treeMap(
    nodeList,
    (node: any, path) => {
      const children = node[options.children] as any as T[] | undefined;
      //如果是错误的节点直接炸掉
      if (!fn(node as T, path)) {
        return null;
      }
      //如果是叶子节点就返回
      if (!children) {
        return node;
      }
      //计算所有子节点中不是 null 的子节点
      const sub = children.filter((node) => node !== null);
      //如果所有子节点为 null 就炸掉
      if (sub.length === 0) {
        return null;
      }
      return {
        ...node,
        children: sub,
      };
    },
    options
  ).filter((node) => node !== null);
}

上面过滤的流程图

treeFilter 流程图.drawio.svg

treeEach

同样的,也是基于 treeMap,其实这个就有点乏善可陈了。

import { TreeOption } from "./treeOption";
import { treeMap } from "./treeMap";

/**
 * 树结构映射
 * 使用深度优先算法
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeEach<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C["id"]][]) => void,
  options: C
) {
  treeMap(
    nodeList,
    (node, path) => {
      fn(node as T, path);
      return node;
    },
    options
  );
}

treeToList

同上。。。

import { TreeOption } from "./treeOption";
import { treeEach } from "./treeEach";

/**
 * 将一个树节点列表压平
 * @param nodeList
 * @param options
 */
export function treeToList<
  T extends object,
  C extends TreeOption<T> & { path: string },
  R extends T & { [K in C["path"]]: NonNullable<T[C["id"]]>[] }
>(nodeList: T[], options: C): R[] {
  const res: R[] = [];
  treeEach(
    nodeList,
    (node, path) => {
      res.push({ ...node, [options.path]: path } as R);
    },
    options
  );
  return res;
}

FAQ

那么,下面是一些泥萌可能存在的一些问题,吾辈在此解答,如有其他问题,可直接在下面评论。

  • 问:为什么不使用 deepdash
  • 答:因为它依赖于 lodash,而且提供的 API 也有点复杂。
  • 问:为什么使用深度优先算法?
  • 答:因为需要兼容 web 框架,例如 react,需要将所有的 JSX 子节点计算完成之后传递给父节点。
  • 问:为什么使用递归而非循环实现?
  • 答:这就是个人纯粹喜好了,循环可以获得更好的性能,但绝大多数情况下,性能并不重要,所以吾辈使用了更为直观的递归。
  • 问:为什么使用 TypeScript 实现?
  • 答:因为 TypeScript 的类型系统对于代码使用者更加友好,也能增强可维护性。– 不过由于 TypeScript 的类型系统过于复杂,所以对于新手不太友好,参考 TypeScript 类型编程

最后,我创建了一个模块 @liuli-util/tree 已经包含了以上功能。


JavaScript 处理树结构数据
https://blog.rxliuli.com/p/7713263c9158489c95009be721e2c6bc/
作者
rxliuli
发布于
2020年2月2日
许可协议