共计 3563 个字符,预计需要花费 9 分钟才能阅读完成。
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.