JavaScript 解决树结构数据
吾辈的博客原文
场景
前端我的项目中，有一些须要解决树结构数据的状况，（一年）之前吾辈已经写过一篇文章，但当初，吾辈有了更好的解决方案。
思考
之前吾辈应用 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[] // 子权限}能够看到，它们都有 id 和 children 字段，只是名字不同。那么，依据封装不变的局部，将变动的局部交予内部输出的封装准则，这两个字段便由内部指定了。
操作
那么，树结构都有哪些操作呢？
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, [])}不过仔细的人可能曾经发现，这里做了两个奇怪的操作
- 先解决了所有子节点，而后将解决后子节点传入到 map 函数中，而非反过来。-- 这其实是为了兼容前端框架 react 的 JSX。
- 计算了节点的
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)}下面过滤的流程图
原图
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 类型编程
Finally, I have created a module @liuli-util/tree that already contains the above functionality.