使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。

支持在 Array、Map、Set、Object 等多种集合类型中查找

findNodeByDFS

函数签名

typescript

function findNodeByDFS<T extends Record<string, any>>(collection: T[] | Map<any, T> | Set<T> | Record<string, T>, compareAttr: string, nextLevelAttr: string, value: unknown)

描述

使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。支持在 Array、Map、Set、Object 等多种集合类型中查找

类型参数

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

参数

参数名	类型	可选	默认值	描述
`collection`	`T[] \| Map<any, T> \| Set<T> \| Record<string, T>`	否	-	-
`compareAttr`	`string`	否	-	-
`nextLevelAttr`	`string`	否	-	-
`value`	`unknown`	否	-	-

返回值

匹配节点的数据、父级数据列表和层级关系

点击查看源码

jsts

/**
 * 检查集合是否非空
 */
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;
}
/**
 * 通用的条目迭代器
 * - 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);
  }
}
/**
 * 使用深度优先搜索（DFS）遍历树形结构，并为每个节点调用回调函数
 * 支持遍历 Array、Map、Set、Object 等多种集合类型
 *
 * @template T - 树节点类型
 * @param {T | T[] | Map | Set | Object | null | undefined} o - 要遍历的树或节点集合
 * @param {keyof T} childrenKey - 子节点属性的键名
 * @param {WalkTreeCallback<T>} cb - 遍历时的回调函数
 */
function walkTree(o, childrenKey, cb) {
  if (!o) return;
  // 保持根节点的原始集合类型
  const rootNodes = Array.isArray(o)
    ? o
    : o instanceof Map || o instanceof Set || typeof o === "object"
      ? o
      : [o];
  let breakLoop = false;
  // DFS递归遍历函数
  function dfsTraverse(nodes, level, ancestors = []) {
    if (!isNonEmptyCollection(nodes)) return false;
    if (breakLoop) return true;
    // 使用 entries 遍历，支持多种集合类型
    for (const [index, node] of entries(nodes)) {
      const typedNode = node;
      const children = typedNode[childrenKey];
      const leaf = !isNonEmptyCollection(children);
      // 调用回调函数
      cb(
        typedNode,
        {
          level,
          index: index,
          leaf,
          peerList: nodes,
          parent: ancestors.slice(-1)[0]?.data,
          ancestors: [...ancestors],
        },
        () => {
          breakLoop = true;
        },
      );
      if (breakLoop) return true;
      if (!leaf) {
        const newAncestors = [...ancestors, { index: index, data: typedNode }];
        if (dfsTraverse(children, level + 1, newAncestors)) return true;
      }
    }
    return false;
  }
  dfsTraverse(rootNodes, 0);
}
/*==========================================  以下为通过 walkTree 实现的函数  ==========================================*/
/**
 * 使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。
 * 支持在 Array、Map、Set、Object 等多种集合类型中查找
 *
 * @template T - 树节点类型
 * @param {T[] | Map | Set | Object} collection - 要进行搜索的集合
 * @param {string} compareAttr - 需要查找的属性名
 * @param {string} nextLevelAttr - 子级循环字段
 * @param {unknown} value - 需要查找的属性值
 * @returns {{ target: T; parent: T | undefined; ancestors: ParentInfo<T>[]; } | undefined} 匹配节点的数据、父级数据列表和层级关系
 */
export function findNodeByDFS(collection, compareAttr, nextLevelAttr, value) {
  let result;
  walkTree(collection, nextLevelAttr, (node, context, breakLoop) => {
    const { parent, ancestors } = context;
    if (node[compareAttr] === value) {
      result = {
        target: node,
        ancestors,
        parent,
      };
      breakLoop();
    }
  });
  return result;
}

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

/**
 * 遍历树的回调函数类型
 * @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;

/**
 * 检查集合是否非空
 */
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;
}

/**
 * 通用的条目迭代器
 * - 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][];
  }
}

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

/**
 * 使用深度优先搜索（DFS）遍历树形结构，并为每个节点调用回调函数
 * 支持遍历 Array、Map、Set、Object 等多种集合类型
 *
 * @template T - 树节点类型
 * @param {T | T[] | Map | Set | Object | null | undefined} o - 要遍历的树或节点集合
 * @param {keyof T} childrenKey - 子节点属性的键名
 * @param {WalkTreeCallback<T>} cb - 遍历时的回调函数
 */
function walkTree<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 rootNodes = Array.isArray(o)
    ? o
    : o instanceof Map || o instanceof Set || typeof o === "object"
      ? o
      : [o];
  let breakLoop = false;

  // DFS递归遍历函数
  function dfsTraverse(
    nodes: any,
    level: number,
    ancestors: ParentInfo<T>[] = [],
  ): boolean {
    if (!isNonEmptyCollection(nodes)) return false;
    if (breakLoop) return true;

    // 使用 entries 遍历，支持多种集合类型
    for (const [index, node] of entries(nodes)) {
      const typedNode = node as T;
      const children = typedNode[childrenKey];
      const leaf = !isNonEmptyCollection(children);

      // 调用回调函数
      cb(
        typedNode,
        {
          level,
          index: index as number | string | T,
          leaf,
          peerList: nodes,
          parent: ancestors.slice(-1)[0]?.data,
          ancestors: [...ancestors],
        },
        () => {
          breakLoop = true;
        },
      );

      if (breakLoop) return true;

      if (!leaf) {
        const newAncestors = [
          ...ancestors,
          { index: index as number | string | T, data: typedNode },
        ];
        if (dfsTraverse(children, level + 1, newAncestors)) return true;
      }
    }

    return false;
  }

  dfsTraverse(rootNodes, 0);
}

/*==========================================  以下为通过 walkTree 实现的函数  ==========================================*/

/**
 * 使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。
 * 支持在 Array、Map、Set、Object 等多种集合类型中查找
 *
 * @template T - 树节点类型
 * @param {T[] | Map | Set | Object} collection - 要进行搜索的集合
 * @param {string} compareAttr - 需要查找的属性名
 * @param {string} nextLevelAttr - 子级循环字段
 * @param {unknown} value - 需要查找的属性值
 * @returns {{ target: T; parent: T | undefined; ancestors: ParentInfo<T>[]; } | undefined} 匹配节点的数据、父级数据列表和层级关系
 */
export function findNodeByDFS<T extends Record<string, any>>(
  collection: T[] | Map<any, T> | Set<T> | Record<string, T>,
  compareAttr: string,
  nextLevelAttr: string,
  value: unknown,
) {
  let result:
    | { target: T; parent: T | undefined; ancestors: ParentInfo<T>[] }
    | undefined;
  walkTree(collection, nextLevelAttr, (node, context, breakLoop) => {
    const { parent, ancestors } = context;

    if (node[compareAttr] === value) {
      result = {
        target: node,
        ancestors,
        parent,
      };
      breakLoop();
    }
  });
  return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

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

使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。 ​

支持在 Array、Map、Set、Object 等多种集合类型中查找 ​

findNodeByDFS ​

函数签名 ​

描述 ​

类型参数 ​

参数 ​

返回值 ​

使用深度优先搜索算法递归查找指定属性值的节点，并返回匹配节点的数据、父级数据列表和层级关系。

支持在 Array、Map、Set、Object 等多种集合类型中查找

findNodeByDFS

函数签名

描述

类型参数

参数

返回值