本教程旨在详细讲解如何从深度嵌套的分类数据结构中，高效地提取并展平指定ID的子节点。文章将介绍一种基于栈的迭代遍历方法，通过巧妙利用 isDesired 标志位，实现对目标分类及其所有后代子节点的收集，同时兼顾了无指定ID时的默认行为以及无子节点时的特殊处理，确保代码的专业性、可读性和性能。
1. 理解嵌套分类数据结构
在许多应用场景中，数据常以树形或嵌套结构存在，例如商品分类、部门层级等。本教程将使用以下示例数据结构，其中每个节点包含 name、id、count 和 children 数组，children 数组可以包含任意深度的子节点。
const data = [ { name: "Car", id: "19", count: "20", depth: "1", children: [ { name: "Wheel", id: "22", count: "3", depth: "2", children: [ { name: "Engine", id: "101", count: "1", depth: "3", children: [ { name: "Engine and Brakes", id: "344", count: "1", depth: "4", children: [] } ] } ] } ] }, { name: "Bike", id: "3", count: "12", depth: "1", children: [ { name: "SpeedBike", id: "4", count: "12", depth: "2", children: [] } ] } ];
我们的目标是从这个复杂结构中，根据一系列指定的分类ID，提取并展平所有对应的子节点。
2. 核心需求分析
针对上述数据结构，我们需要实现以下功能：
- 提取指定ID的子节点并展平： 给定一个分类ID数组（例如 [’22’, ‘3’]），返回这些ID所对应的所有子节点（包括子节点的子节点，直到最深层），并将它们展平为一个单一列表。返回的节点只包含 name、id、count 属性。
// 预期输出示例 [ { name: "Engine", id: "101", count: "1" }, { name: "Engine and Brakes", id: "344", count: "1" }, { name: "SpeedBike", id: "4", count: "12" } ] - 默认行为（无指定ID时）： 如果没有提供任何分类ID，则返回所有顶级父节点及其直接子节点。
// 预期输出示例 [ { name: "Car", id: "19", count: "20" }, { name: "Wheel", id: "22", count: "3" }, { name: "Bike", id: "3", count: "12" }, { name: "SpeedBike", id: "4", count: "12" } ] - 处理无子节点的情况： 如果指定的分类ID存在，但该分类本身没有子节点，则返回一个空数组 []。
3. 解决方案设计：基于栈的迭代遍历
为了高效处理深度嵌套结构并避免传统的 for/foreach 循环（在主遍历逻辑中），我们将采用一种基于栈的迭代遍历策略。这种方法能够很好地模拟递归，但避免了递归深度限制，并且易于控制遍历过程。
核心思路：
- 辅助映射函数 mapCategory： 用于将完整的分类对象映射为只包含 name、id、count 的精简对象。
- 默认情况处理： 当 categoryIds 为空时，使用 Array.prototype.reduce 遍历顶级分类，收集它们自身和直接子节点。
- 栈式遍历：
- 初始化一个栈，将所有顶级分类放入栈中。
- 在每个栈元素中，引入一个 isDesired 标志位。如果一个分类是目标ID的子节点，或者其祖先是目标ID，则此标志位为 true。
- 循环从栈中取出分类：
- 如果当前分类的ID在 categoryIds 中，或者它的 isDesired 标志为 true，则将其所有子节点（通过 mapCategory 转换后）添加到 foundChildren 结果数组中。
- 将当前分类的子节点重新推入栈中。如果 isDesiredCategory 为 true，则子节点在推入栈时也带上 isDesired: true 标志，以确保其所有后代都会被收集。
4. 示例代码实现
首先定义类型（typescript），以便更好地理解数据结构：
interface Category { name: string; id: string; count: string; depth: string; children: Category[]; } // 辅助函数：将完整分类对象映射为精简对象 const mapCategory = (category: Category) => ({ name: category.name, id: category.id, count: category.count, }); /** * 从嵌套分类数据中提取并展平指定ID的子节点。 * * @param categoryIds 目标分类ID数组。如果为空，则返回所有顶级分类及其直接子节点。 * @param categories 完整的分类数据数组。 * @returns 展平后的子节点列表。 */ const getCategoriesChildren = ( categoryIds: Category['id'][], categories: Category[], ): Pick<Category, 'id' | 'count' | 'name'>[] => { const foundChildren: Pick<Category, 'id' | 'count' | 'name'>[] = []; // 情况1: 如果没有指定任何分类ID，返回所有父节点及其直接子节点 if (categoryIds.Length === 0) { return categories.reduce<Pick<Category, 'id' | 'count' | 'name'>[]>( (acc, category) => { acc.push(mapCategory(category)); // 添加父节点 acc.push(...category.children.map(mapCategory)); // 添加直接子节点 return acc; }, [], ); } // 情况2: 处理指定分类ID的子节点提取 // 栈用于迭代遍历所有分类，并追踪是否为目标ID的后代 const stack: (Category & { isDesired?: Boolean })[] = [...categories]; while (stack.length) { const category = stack.pop(); // 从栈顶取出分类 if (!category) continue; // 确保分类存在 // 判断当前分类是否是期望的分类（即其ID在categoryIds中，或者它是某个期望分类的后代） const isDesiredCategory = categoryIds.includes(category.id) || category.isDesired; // 如果是期望分类，则将其所有直接子节点添加到结果列表中 if (isDesiredCategory) { foundChildren.push(...category.children.map(mapCategory)); } // 将当前分类的子节点推入栈中，继续遍历 // 如果当前分类是期望分类，则其子节点也应被标记为 isDesired: true stack.push( ...(isDesiredCategory ? category.children.map((child) => ({ ...child, isDesired: true })) : category.children), ); } return foundChildren; };
5. 详细解释与使用示例
5.1 默认行为 (categoryIds.length === 0)
当 categoryIds 数组为空时，函数会进入第一个 if 块。这里使用 reduce 方法遍历顶层 categories。对于每个顶层 category，我们首先通过 mapCategory 添加其自身，然后通过 …category.children.map(mapCategory) 将其所有直接子节点也添加到结果数组中。
// 示例数据 const data = [/* ...同上 */]; // 情况1: 没有指定分类ID，获取所有父节点及其直接子节点 const defaultResult = getCategoriesChildren([], data); console.log('默认结果:', defaultResult); /* [ { name: "Car", id: "19", count: "20" }, { name: "Wheel", id: "22", count: "3" }, { name: "Bike", id: "3", count: "12" }, { name: "SpeedBike", id: "4", count: "12" } ] */
5.2 指定分类ID的子节点提取
当 categoryIds 不为空时，我们进入基于栈的迭代遍历逻辑。
-
初始化栈： const stack: (Category & { isDesired?: boolean })[] = […categories]; 我们将所有顶级分类推入栈中。此时，它们都没有 isDesired 标志。
-
while (stack.length) 循环： 只要栈不为空，就继续处理。stack.pop() 会取出栈顶元素，实现深度优先遍历的逻辑。
-
isDesiredCategory 判断：
- categoryIds.includes(category.id)：检查当前分类的ID是否在传入的目标ID列表中。
- category.isDesired：检查当前分类是否是某个目标分类的后代。这个标志位是从其祖先继承下来的。
-
收集子节点： if (isDesiredCategory) { foundChildren.push(…category.children.map(mapCategory)); } 如果当前分类是目标分类（或其后代），则将其 所有直接子节点 映射并添加到 foundChildren 数组中。注意，这里只添加了直接子节点，但由于后续会将这些子节点重新推入栈中，它们自身的子节点也会在后续循环中被处理。
-
更新栈： stack.push(…) 这是算法的关键部分。我们将当前分类的子节点重新推入栈中，以便在下一次迭代中处理它们。
- isDesiredCategory ? category.children.map((child) => ({ …child, isDesired: true })) : category.children 如果当前分类是期望的，那么它的所有子节点在推入栈时，都会被赋予 isDesired: true 标志。这意味着这些子节点（以及它们的后代）在后续处理中，即使它们的ID不在 categoryIds 中，也会因为 isDesired 标志而被视为“期望的后代”，从而将其自身的子节点也添加到 foundChildren 中。
// 示例数据 const data = [/* ...同上 */]; // 情况2: 指定分类ID，获取其所有子节点 const specificIdsResult = getCategoriesChildren(['22', '3'], data); console.log('指定ID结果:', specificIdsResult); /* [ { name: "Engine", id: "101", count: "1" }, { name: "Engine and Brakes", id: "344", count: "1" }, { name: "SpeedBike", id: "4", count: "12" } ] */ // 情况3: 指定ID但该分类无子节点 const noChildrenResult = getCategoriesChildren(['4'], data); // SpeedBike 的 ID 是 '4'，它没有子节点 console.log('无子节点结果:', noChildrenResult); // 预期输出: [] /* [] */ // 进一步测试：指定一个不存在的ID const nonExistentIdResult = getCategoriesChildren(['999'], data); console.log('不存在ID结果:', nonExistentIdResult); // 预期输出: [] /* [] */
6. 注意事项与总结
- 避免传统循环的解释： 尽管代码中使用了 while (stack.length)，但它主要用于管理栈的迭代过程，而非传统意义上的 for (let i=0; i<arr.length; i++) 或 forEach 来直接遍历数据并执行主要业务逻辑。核心的数据处理和转换（如 map、push 与展开运算符）体现了更函数式的风格。
- 性能考量： 栈式迭代方法对于深度嵌套结构具有良好的性能，避免了递归深度限制。每次 pop 和 push 操作都是常数时间复杂度。
- 内存使用： 栈的深度取决于数据结构的最大深度，而栈中存储的对象数量则取决于节点总数。对于非常庞大的树形结构，需要注意内存消耗。
- 灵活性： 这种带有 isDesired 标志的迭代方法非常灵活，可以轻松扩展以处理其他复杂的筛选逻辑，例如只获取特定深度的子节点，或根据其他属性进行筛选。
通过本文介绍的基于栈的迭代遍历策略，我们能够高效、灵活地从深度嵌套的分类数据中提取并展平指定子节点，同时满足多种复杂场景的需求。这种方法在处理树形数据结构时具有很高的实用价值。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
