tree

树结构遍历工具，支持深度优先和广度优先遍历。

导入

import {
  treeEach,
  treeFind,
  deepFlat,
  treeFrom,
  type TreeItem,
  type TreeList,
  type TreeWalker,
  type TreeInfo,
  type TreeEachIterator,
  type TreeEachIteratorAsync,
  type TreeWalk,
  type TreeWalkAsync,
  type TreeFromOptions,
  type FromItemInfo,
} from '@cloudcome/utils-core/tree';

类型定义

TreeItem

树节点类型。

type TreeItem = AnyObject & {
  children?: TreeItem[];
};

TreeList<I>

树节点列表类型。

type TreeList<I extends TreeItem> = I[];

TreeWalker<I>

遍历器状态。

type TreeWalker<I extends TreeItem> = {
  list: TreeList<I>;
  parent: I | null;
  level: number;
  path: TreeList<I>;
};

属性说明

属性	类型	描述
list	TreeList<I>	当前层级的节点列表
parent	I | null	当前节点的父节点，根节点为 null
level	number	当前节点的层级，从 1 开始
path	TreeList<I>	从根节点到当前节点的路径

TreeInfo<I>

遍历节点信息。

type TreeInfo<I extends TreeItem> = TreeWalker<I> & {
  item: I;
  index: number;
};

属性说明

属性	类型	描述
item	I	当前节点
index	number	当前节点在 list 中的索引

TreeEachIterator<I>

同步迭代器函数类型。

type TreeEachIterator<I extends TreeItem> = (info: TreeInfo<I>) => false | unknown;

TreeEachIteratorAsync<I>

异步迭代器函数类型。

type TreeEachIteratorAsync<I extends TreeItem> = (info: TreeInfo<I>) => Promise<boolean | unknown>;

TreeWalk<I>

同步遍历器函数类型，用于自定义遍历逻辑。

type TreeWalk<I extends TreeItem> = (walker: TreeWalker<I>) => unknown;

TreeWalkAsync<I>

异步遍历器函数类型，用于自定义异步遍历逻辑。

type TreeWalkAsync<I extends TreeItem> = (walker: TreeWalker<I>) => Promise<unknown>;

TreeFromOptions<I>

从列表构建树的配置选项。

type TreeFromOptions<I extends TreeItem> = {
  getSelfKey: (item: I, index: number) => unknown;
  getParentKey: (item: I, index: number) => unknown;
  appendChild: (
    parentInfo: {
      selfKey: unknown;
      parentKey: unknown;
      item: I;
      index: number;
    },
    info: {
      selfKey: unknown;
      parentKey: unknown;
      item: I;
      index: number;
    },
  ) => unknown;
};

属性说明

属性	类型	描述
getSelfKey	(item: I, index: number) => unknown	获取节点自身唯一标识的函数
getParentKey	(item: I, index: number) => unknown	获取节点父节点唯一标识的函数
appendChild	(parentInfo, info) => unknown	将子节点添加到父节点的函数

函数

treeEach

深度遍历树结构中的每个节点。

function treeEach<I extends TreeItem = TreeItem>(
  treeList: TreeList<I>,
  iterator: TreeEachIterator<I>,
  breadthFirst?: boolean,
): void;

参数

参数	类型	默认值	描述
treeList	TreeList<I>	-	要遍历的树结构数组
iterator	TreeEachIterator<I>	-	对每个节点执行的回调函数，返回 false 可提前终止
breadthFirst	boolean	false	是否使用广度优先遍历，默认深度优先

返回值

void

示例

const tree = [
  {
    id: 1,
    children: [{ id: 2 }, { id: 3, children: [{ id: 4 }] }],
  },
];

// 深度优先遍历（默认）
treeEach(tree, (info) => {
  console.log(`Level ${info.level}:`, info.item.id);
});
// Level 1: 1
// Level 2: 2
// Level 2: 3
// Level 3: 4

// 广度优先遍历
treeEach(
  tree,
  (info) => {
    console.log(`Level ${info.level}:`, info.item.id);
  },
  true,
);
// Level 1: 1
// Level 2: 2
// Level 2: 3
// Level 3: 4

// 提前终止
treeEach(tree, (info) => {
  if (info.item.id === 2) return false;
  console.log(info.item.id);
});
// 1

treeFind

在树结构中查找符合条件的节点，返回节点的完整信息（包含节点本身、层级、路径等）。

function treeFind<I extends TreeItem>(
  treeList: TreeList<I>,
  predicate: (info: TreeInfo<I>) => boolean,
  breadthFirst?: boolean,
): TreeInfo<I> | undefined;

参数

参数	类型	默认值	描述
treeList	TreeList<I>	-	要查找的树结构数组
predicate	(info: TreeInfo<I>) => boolean	-	判断条件函数
breadthFirst	boolean	false	是否使用广度优先查找，默认深度优先

返回值

TreeInfo<I> | undefined - 找到的节点信息（包含 item、index、level、parent、path 等），未找到返回 undefined

示例

const tree = [
  {
    id: 1,
    children: [{ id: 2 }, { id: 3, children: [{ id: 4 }] }],
  },
];

const found = treeFind(tree, (info) => info.item.id === 3);
// {
//   item: { id: 3, children: [{ id: 4 }] },
//   index: 1,
//   list: [{ id: 2 }, { id: 3, children: [{ id: 4 }] }],
//   parent: { id: 1, children: [...] },
//   level: 2,
//   path: [{ id: 1, children: [...] }, { id: 3, children: [...] }]
// }

const notFound = treeFind(tree, (info) => info.item.id === 99);
// undefined

deepFlat

将树结构扁平化为一维数组。

function deepFlat<I extends TreeItem, T>(
  treeList: TreeList<I>,
  mapper: (info: TreeInfo<I>) => T,
  breadthFirst?: boolean,
): T[];

参数

参数	类型	默认值	描述
treeList	TreeList<I>	-	要扁平化的树结构数组
mapper	(info: TreeInfo<I>) => T	-	映射函数，将节点转换为目标类型
breadthFirst	boolean	false	是否使用广度优先遍历

返回值

T[] - 扁平化后的数组

示例

const tree = [
  {
    id: 1,
    children: [{ id: 2 }, { id: 3, children: [{ id: 4 }] }],
  },
];

deepFlat(tree, (info) => info.item.id);
// [1, 2, 3, 4]

deepFlat(tree, (info) => ({ id: info.item.id, level: info.level }));
// [
//   { id: 1, level: 1 },
//   { id: 2, level: 2 },
//   { id: 3, level: 2 },
//   { id: 4, level: 3 }
// ]

treeFrom

从扁平列表构建树结构。

function treeFrom<I extends TreeItem>(list: I[], options: TreeFromOptions<I>): TreeList<I> | undefined;

参数

参数	类型	描述
list	I[]	扁平列表
options	TreeFromOptions<I>	配置选项

返回值

TreeList<I> | undefined - 构建的树结构

示例

const list = [
  { id: 1, parentId: null },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 3 },
];

const tree = treeFrom(list, {
  getSelfKey: (item) => item.id,
  getParentKey: (item) => item.parentId,
  appendChild: (parent, child) => {
    if (!parent.item.children) parent.item.children = [];
    parent.item.children.push(child.item);
  },
});
// [
//   {
//     id: 1, parentId: null,
//     children: [
//       { id: 2, parentId: 1 },
//       { id: 3, parentId: 1, children: [{ id: 4, parentId: 3 }] }
//     ]
//   }
// ]