@utilslib

Appearance

@utilslib/core/walkTreeBFS

使用广度优先搜索（BFS）遍历树形结构，并为每个节点调用回调函数 ​

支持遍历 Array、Map、Set、Object 等多种集合类型 ​

walkTreeBFS ​

函数签名 ​

typescript
function walkTreeBFS<T extends Record<string, any>, K extends keyof T>(o: T | T[] | Map<any, T> | Set<T> | Record<string, T> | null | undefined, childrenKey: K, cb: WalkTreeCallback<T>): void

描述 ​

使用广度优先搜索（BFS）遍历树形结构，并为每个节点调用回调函数 支持遍历 Array、Map、Set、Object 等多种集合类型

类型参数 ​

参数名约束默认值描述
TRecord<string, any>-- 树节点类型
Kkeyof T--

参数 ​

参数名类型可选默认值描述
oT | T[] | Map<any, T> | Set<T> | Record<string, T> | null | undefined否--
childrenKeyK否--
cbWalkTreeCallback<T>否--

返回值 ​

void

点击查看源码
js
/**
 * 通用的条目迭代器
 * - Map: [key, value]
 * - Set: [value, value]
 * - Array/Iterable: [index, value]
 * - Object: [key, value]
 */
function* entries(data) {
  if (data instanceof Map) yield* data;
  else if (data instanceof Set) {
    for (const v of data) yield [v, v];
  } else if (typeof data[Symbol.iterator] === "function") {
    let i = 0;
    for (const v of data) yield [i++, v];
  } else if (data) {
    yield* Object.entries(data);
  }
}
/**
 * 检查集合是否非空
 */
function isNonEmptyCollection(data) {
  if (!data) return false;
  if (Array.isArray(data)) return data.length > 0;
  if (data instanceof Map || data instanceof Set) return data.size > 0;
  if (typeof data === "object") return Object.keys(data).length > 0;
  return false;
}
/**
 * 使用广度优先搜索（BFS）遍历树形结构，并为每个节点调用回调函数
 * 支持遍历 Array、Map、Set、Object 等多种集合类型
 *
 * @template T - 树节点类型
 * @param {T | T[] | Map | Set | Object | null | undefined} o - 要遍历的树或节点集合
 * @param {keyof T} childrenKey - 子节点属性的键名
 * @param {WalkTreeCallback<T>} cb - 遍历时的回调函数
 */
export function walkTreeBFS(o, childrenKey, cb) {
  if (!o) return;
  // 初始化队列，支持多种集合类型
  const queue = [];
  // 将根节点添加到队列
  const rootNodes = Array.isArray(o)
    ? o
    : o instanceof Map || o instanceof Set || typeof o === "object"
      ? o
      : [o];
  for (const [index, node] of entries(rootNodes)) {
    queue.push({ node: node, level: 0, index: index, ancestors: [] });
  }
  let shouldBreak = false;
  while (queue.length && !shouldBreak) {
    const { node, level, index, ancestors } = queue.shift();
    const children = node[childrenKey];
    const leaf = !isNonEmptyCollection(children);
    // 调用回调函数
    cb(
      node,
      {
        level,
        index,
        leaf,
        peerList: [], // BFS模式下同级列表不易获取
        parent: ancestors.slice(-1)[0]?.data,
        ancestors: [...ancestors],
      },
      () => {
        shouldBreak = true; // 标记需要中断遍历，直接影响while循环条件
      },
    );
    // 如果没有中断并且节点有子节点，则将子节点添加到队列
    if (!shouldBreak && !leaf && isNonEmptyCollection(children)) {
      for (const [childIndex, child] of entries(children)) {
        queue.push({
          node: child,
          level: level + 1,
          index: childIndex,
          ancestors: [...ancestors, { index, data: node }],
        });
      }
    }
  }
}
ts
/**
 * 遍历树的回调函数类型
 * @template T - 树节点类型
 * @template C - 子节点集合类型
 */
type WalkTreeCallback<T, C = any> = (
  item: T,
  context: {
    /** 当前节点的层级 */
    level: number;
    /** 当前节点在同级节点中的索引（数组为number，Map/Object为key，Set为值本身） */
    index: number | string | T;
    /** 当前节点是否为叶子节点 */
    leaf: boolean;
    /** 当前节点的同级节点列表（保持原始集合类型） */
    peerList: C;
    /** 当前节点的父节点信息 */
    parent?: T;
    /** 当前节点的所有祖先节点列表 */
    ancestors: ParentInfo<T>[];
  },
  // 停止遍历
  breakLoop: () => void,
) => void;

/**
 * 父节点信息接口
 * @template T - 树节点类型
 */
export interface ParentInfo<T> {
  /** 在同级节点中的索引（数组为number，Map/Object为key，Set为值本身） */
  index: number | string | T;
  /** 父节点数据 */
  data: T;
}

/**
 * 通用的条目迭代器
 * - Map: [key, value]
 * - Set: [value, value]
 * - Array/Iterable: [index, value]
 * - Object: [key, value]
 */
function* entries<T, K, V>(
  data: Map<K, V> | Set<T> | Iterable<T> | Record<string, any>,
): Generator<[K | number | string | T, V | T], void, unknown> {
  if (data instanceof Map) yield* data;
  else if (data instanceof Set) {
    for (const v of data) yield [v, v] as [T, T];
  } else if (typeof (data as Iterable<T>)[Symbol.iterator] === "function") {
    let i = 0;
    for (const v of data as Iterable<T>) yield [i++, v] as [number, T];
  } else if (data) {
    yield* Object.entries(data) as [string, any][];
  }
}

/**
 * 检查集合是否非空
 */
function isNonEmptyCollection(data: any): boolean {
  if (!data) return false;
  if (Array.isArray(data)) return data.length > 0;
  if (data instanceof Map || data instanceof Set) return data.size > 0;
  if (typeof data === "object") return Object.keys(data).length > 0;
  return false;
}

/**
 * 使用广度优先搜索（BFS）遍历树形结构，并为每个节点调用回调函数
 * 支持遍历 Array、Map、Set、Object 等多种集合类型
 *
 * @template T - 树节点类型
 * @param {T | T[] | Map | Set | Object | null | undefined} o - 要遍历的树或节点集合
 * @param {keyof T} childrenKey - 子节点属性的键名
 * @param {WalkTreeCallback<T>} cb - 遍历时的回调函数
 */
export function walkTreeBFS<T extends Record<string, any>, K extends keyof T>(
  o: T | T[] | Map<any, T> | Set<T> | Record<string, T> | null | undefined,
  childrenKey: K,
  cb: WalkTreeCallback<T>,
): void {
  if (!o) return;

  // 初始化队列，支持多种集合类型
  const queue: Array<{
    node: T;
    level: number;
    index: number | string | T;
    ancestors: ParentInfo<T>[];
  }> = [];

  // 将根节点添加到队列
  const rootNodes = Array.isArray(o)
    ? o
    : o instanceof Map || o instanceof Set || typeof o === "object"
      ? o
      : [o];
  for (const [index, node] of entries(rootNodes)) {
    queue.push({
      node: node as T,
      level: 0,
      index: index as number | string | T,
      ancestors: [],
    });
  }

  let shouldBreak = false;

  while (queue.length && !shouldBreak) {
    const { node, level, index, ancestors } = queue.shift()!;
    const children = node[childrenKey];
    const leaf = !isNonEmptyCollection(children);

    // 调用回调函数
    cb(
      node,
      {
        level,
        index,
        leaf,
        peerList: [], // BFS模式下同级列表不易获取
        parent: ancestors.slice(-1)[0]?.data,
        ancestors: [...ancestors],
      },
      () => {
        shouldBreak = true; // 标记需要中断遍历，直接影响while循环条件
      },
    );

    // 如果没有中断并且节点有子节点，则将子节点添加到队列
    if (!shouldBreak && !leaf && isNonEmptyCollection(children)) {
      for (const [childIndex, child] of entries(children)) {
        queue.push({
          node: child as T,
          level: level + 1,
          index: childIndex as number | string | T,
          ancestors: [...ancestors, { index, data: node }],
        });
      }
    }
  }
}

如有错误，请提交issue :::