【JS】JavaScript 处理树结构数据

• Z时代
• 2024-01-10
• 分类：技术分享

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

interface SysMenu {
id: number // 菜单 id
name: string // 显示的名称
sub: SysMenu[] // 子级菜单
}
interface SysPermission {
uid: string // 系统唯一 uuid
label: string // 显示的菜单名
children: SysPermission[] // 子权限
}

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

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, [])
}

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)
}

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,
)
}

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
}

JavaScript 处理树结构数据

场景

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

思考

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

其实树结构数据可以抽象出非常简单的 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 的字段名是什么，便于内部实现读取树节点信息。

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)
}

上面过滤的流程图

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 类型编程

以上是 【JS】JavaScript 处理树结构数据 的全部内容， 来源链接： utcz.com/a/111514.html