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[] => {
const foundChildren: Pick[] = [];
// 情况1: 如果没有指定任何分类ID，返回所有父节点及其直接子节点
if (categoryIds.length === 0) {
return categories.reduce[]>(
(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
- 性能考量： 栈式迭代方法对于深度嵌套结构具有良好的性能，避免了递归深度限制。每次 pop 和 push 操作都是常数时间复杂度。
- 内存使用： 栈的深度取决于数据结构的最大深度，而栈中存储的对象数量则取决于节点总数。对于非常庞大的树形结构，需要注意内存消耗。
- 灵活性： 这种带有 isDesired 标志的迭代方法非常灵活，可以轻松扩展以处理其他复杂的筛选逻辑，例如只获取特定深度的子节点，或根据其他属性进行筛选。
通过本文介绍的基于栈的迭代遍历策略，我们能够高效、灵活地从深度嵌套的分类数据中提取并展平指定子节点，同时满足多种复杂场景的需求。这种方法在处理树形数据结构时具有很高的实用价值。
