wtreemap

树形关系在 Map 中的常用处理工具库

安装

npm install wtreemap

使用示例

import treemap from 'wtreemap';

// 创建正向树（上级指向子级列表）
const tree = new Map([
    ['A', ['B', 'C']],
    ['B', ['D']]
]);

// 转换为反向树（子级指向上级）
const upperTree = treemap.toUpper(tree);
// Map([
//     ['A', undefined],
//     ['B', 'A'],
//     ['C', 'A'],
//     ['D', 'B']
// ])

// 判断节点关系
treemap.isUpper(upperTree, 'D', 'A'); // true
treemap.isLower(tree, 'A', 'D'); // true

// 获取节点路径
treemap.listUpper(upperTree, 'D'); // ['D', 'B', 'A']
treemap.listLower(tree, 'A'); // ['A', 'B', 'C', 'D']

API 文档

基础转换

toUpper(tree: Map<T, T[] | undefined>): Map<T, T | undefined>

将正向树(上级指向子级列表)转为反向树(子级指向上级)

• 例如：A->[B,C] 转为 B->A, C->A

const tree = new Map([['A', ['B', 'C']]]);
const upperTree = treemap.toUpper(tree);
// Map([['A', undefined], ['B', 'A'], ['C', 'A']])

toLower(tree: Map<T, T | undefined>): Map<T, T[] | undefined>

将反向树(子级指向上级)转为正向树(上级指向子级列表)

• 例如：B->A, C->A 转为 A->[B,C]

const upperTree = new Map([['B', 'A'], ['C', 'A']]);
const tree = treemap.toLower(upperTree);
// Map([['A', ['B', 'C']]])

reverse(tree: Map<T, T[] | undefined>): Map<T, T[] | undefined>

反转多对多树关系

• 例如：A->[B,C], B->[C] 转为 B->[A], C->[A,B]

const tree = new Map([['A', ['B', 'C']], ['B', ['C']]]);
const reversed = treemap.reverse(tree);
// Map([['B', ['A']], ['C', ['A', 'B']]])

关系判断

isUpper(tree: Map<T, T | undefined>, lower: T, upper: T): boolean

判断下级节点是否是上级节点的子孙节点

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.isUpper(upperTree, 'C', 'A'); // true
treemap.isUpper(upperTree, 'B', 'C'); // false

isLower(tree: Map<T, T[] | undefined>, upper: T, lower: T): boolean

判断上级节点是否是下级节点的祖先节点

const tree = new Map([['A', ['B']], ['B', ['C']]]);
treemap.isLower(tree, 'A', 'C'); // true
treemap.isLower(tree, 'B', 'A'); // false

hasUpper(tree: Map<T, T | undefined>, lower: T, isUpper: (value: T) => boolean): boolean

判断下级节点是否有满足条件的上级节点

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.hasUpper(upperTree, 'C', (node) => node === 'A'); // true

getUpper(tree: Map<T, T | undefined>, lower: T, isUpper: (value: T) => boolean): T | undefined

获取下级节点中第一个满足条件的上级节点

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.getUpper(upperTree, 'C', (node) => node === 'A'); // 'A'

层级操作

getLevel(tree: Map<T, T | undefined>, value: T): number

获取指定树节点的层级

• 根节点层级为0，每向下一层加1
• 如果节点不在树中则返回-1

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.getLevel(upperTree, 'A'); // 0
treemap.getLevel(upperTree, 'B'); // 1
treemap.getLevel(upperTree, 'C'); // 2

getLevels(tree: Map<T, T | undefined>, values?: T[]): Map<T, number>

获取指定树节点数组的层级字典

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.getLevels(upperTree, ['A', 'B', 'C']);
// Map([['A', 0], ['B', 1], ['C', 2]])

路径操作

mapUpper(tree: Map<T, T | undefined>, filter: Iterable): Map<T, T | undefined>

获取指定节点列表的所有上级路径

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.mapUpper(upperTree, ['C']);
// Map([['C', 'B'], ['B', 'A']])

mapFilter(tree: Map<T, T | undefined>, filter: Iterable): Map<T, T | undefined>

过滤简化树，只保留指定节点及其直接上级节点

const upperTree = new Map([['B', 'A'], ['C', 'B'], ['D', 'A']]);
treemap.mapFilter(upperTree, ['B', 'C', 'D']);
// Map([['B', 'A'], ['C', 'B'], ['D', 'A']])

// 当只过滤 B 和 C 时
treemap.mapFilter(upperTree, ['B', 'C']);
// Map([['B', 'A'], ['C', 'B']])

// 当只过滤 A 和 C 时
treemap.mapFilter(upperTree, ['A', 'C']);
// Map([['A', undefined], ['C', 'A']])

listUpper(tree: Map<T, T | undefined>, lower: T): T[]

获取指定节点的上级节点路径列表（从当前节点到根节点）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.listUpper(upperTree, 'C'); // ['C', 'B', 'A']

listUppers(tree: Map<T, T | undefined>, lowers: T[]): T[]

获取指定节点列表的上级节点路径列表（合并所有节点的上级路径并去重）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.listUppers(upperTree, ['B', 'C']); // ['B', 'A', 'C']

listLower(tree: Map<T, T[] | undefined>, root: T): T[]

从正向树中获取指定根节点的所有下级列表（广度优先遍历）

const tree = new Map([['A', ['B', 'C']], ['B', ['D']]]);
treemap.listLower(tree, 'A'); // ['A', 'B', 'C', 'D']

listLowers(tree: Map<T, T[] | undefined>, roots: T[]): T[]

从正向树中获取指定根节点列表的所有下级列表（合并所有根节点的下级列表并去重）

const tree = new Map([['A', ['B']], ['C', ['D']]]);
treemap.listLowers(tree, ['A', 'C']); // ['A', 'B', 'C', 'D']

listPath(tree: Map<T, T | undefined>, start: T, end: T): T[]

根据拓扑树获取两个节点间的路径列表（查找最短路径）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.listPath(upperTree, 'C', 'A'); // ['C', 'B', 'A']

截取操作

subUpper(tree: Map<T, T | undefined>, lower: T, filter?: (child: T, parent: T) => boolean): T[]

截取指定节点的上级节点路径列表（从当前节点向上遍历，直到不满足条件）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.subUpper(upperTree, 'C', (child, parent) => parent !== 'A'); // ['C', 'B']

subUppers(tree: Map<T, T | undefined>, lowers: T[], filter?: (child: T, parent: T) => boolean): Set

批量获取元素去重上级（获取所有节点的上级节点并去重）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.subUppers(upperTree, ['B', 'C']); // Set(['A', 'B'])

subLower(tree: Map<T, T[] | undefined>, root: T, filter?: (child: T, parent: T) => boolean): T[]

截取指定根节点的所有下级列表（从根节点向下遍历，只保留满足条件的节点）

const tree = new Map([['A', ['B', 'C']], ['B', ['D']]]);
treemap.subLower(tree, 'A', (child, parent) => parent !== 'B'); // ['A', 'C']

subLowers(tree: Map<T, T[] | undefined>, roots: T[], filter?: (child: T, parent: T) => boolean): Set

截取指定根节点的所有下级列表（从多个根节点向下遍历，只保留满足条件的节点）

const tree = new Map([['A', ['B']], ['C', ['D']]]);
treemap.subLowers(tree, ['A', 'C'], (child, parent) => parent !== 'A'); // Set(['C', 'D'])

特殊节点

listRoot(tree: Map<T, T | undefined>, result: T[] = []): T[]

遍历树获取所有根节点（没有父节点的节点）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.listRoot(upperTree); // ['A']

listTail(tree: Map<T, T | undefined>, result: T[] = []): T[]

遍历树获取所有叶子节点（没有子节点的节点）

const upperTree = new Map([['B', 'A'], ['C', 'B']]);
treemap.listTail(upperTree); // ['C']

类型说明

• T: 树节点的类型
• Map<T, T[] | undefined>: 正向树，键为上级节点，值为下级节点列表
• Map<T, T | undefined>: 反向树，键为下级节点，值为上级节点

注意事项

1. 所有方法都保持原有树结构不变
2. 对于不存在的节点会返回 undefined
3. 所有返回数组的方法都保证顺序性
4. 所有返回集合的方法都保证唯一性

作者

王怀

许可证

MIT