本教程探讨如何从包含多层嵌套对象的数组中，根据对象的type属性高效地提取特定元素。我们将介绍一种基于栈的迭代遍历算法，它能够有效处理任意深度的嵌套结构，避免递归可能带来的栈溢出问题，并提供详细的代码实现与注意事项，帮助开发者精确筛选所需数据。
引言
在现代前端或后端开发中，处理复杂的数据结构是常见任务。尤其当数据以深层嵌套的数组和对象形式存在时，如何高效、准确地从中筛选出符合特定条件的元素，成为一个值得探讨的问题。本文将聚焦于一种典型的场景：从一个包含多层items（子项）嵌套的数组中，根据对象的type属性提取所有匹配的元素。
问题场景分析
假设我们有一个JSON数据结构，它是一个对象数组，其中每个对象可能包含一个items属性，而items本身又是一个包含类似对象的数组，如此循环往复，形成一个树状或图状的嵌套结构。每个对象都有一个type属性，我们需要找出所有type为特定值（例如 "text"）的对象，无论它们嵌套在哪个层级。
以下是示例数据结构的一部分，展示了这种嵌套特性：
[
{
"index": 3,
"uid": "188960ecb29_00562b0c",
"type": "group",
"items": [
{
"uid": "18895f59b1a_2c5a5c7a",
"type": "text", // 目标类型
"text": ["abc"]
},
{
"index": 1,
"type": "group",
"items": [
{
"uid": "18895ecc7c7_2d5440b6",
"type": "text", // 目标类型
"text": ["xyz"]
}
]
}
]
}
]解决方案：基于栈的迭代遍历
处理深层嵌套结构通常有两种主要方法：递归和迭代。虽然递归在概念上更直观，但它可能面临栈溢出（Stack Overflow）的风险，尤其是在处理非常深的数据结构时。因此，我们推荐使用基于栈的迭代遍历方法，它能有效规避这一问题。
算法原理
- 初始化结果数组和栈： 创建一个空数组用于存储符合条件的对象，并创建一个栈，将初始的顶层元素全部推入栈中。
-
循环遍历： 当栈不为空时，持续执行以下步骤：
- 弹出元素： 从栈顶弹出一个元素（当前处理的对象）。
- 条件判断： 检查当前元素的type属性是否与目标类型匹配。如果匹配，则将其添加到结果数组中。
- 处理子项： 检查当前元素是否包含items属性。如果存在且items是一个非空数组，则将其所有子项（items中的每个元素）推入栈中。这样可以确保在后续迭代中访问到所有嵌套层级的元素。
- 返回结果： 栈为空时，表示所有元素都已遍历完毕，返回结果数组。
代码实现
以下是使用 TypeScript 实现该算法的示例代码：
interface Item {
type: string;
items?: Item[]; // 子项可以是可选的
[key: string]: any; // 允许其他任意属性
}
/**
* 从嵌套对象数组中提取所有指定类型的对象
* @param data 原始的嵌套对象数组
* @param targetType 目标对象的类型字符串
* @returns 包含所有匹配对象的数组
*/
const getSpecificType = (data: Item[], targetType: string): Item[] => {
const result: Item[] = [];
// 使用展开运算符将初始数据复制到栈中，避免修改原始数据
const stack: Item[] = [...data];
while (stack.length > 0) {
// 从栈顶弹出一个元素进行处理
const current = stack.pop();
// 确保弹出的元素存在
if (!current) {
continue;
}
// 检查当前元素的类型是否匹配目标类型
if (current.type === targetType) {
result.push(current);
}
// 如果当前元素有子项 (items)，则将它们推入栈中
// 使用 ?? [] 确保即使 items 为 undefined 或 null 也能安全处理
if (current.items && current.items.length > 0) {
// 将子项反向推入栈中，以保持从左到右的遍历顺序（如果需要）
// 或者直接 push 保持 DFS 顺序
stack.push(...current.items);
}
}
return result;
};
// 示例数据（与问题内容一致）
const nestedData: Item[] = [
{
"index": 3,
"uid": "188960ecb29_00562b0c",
"x": 18.651406278454424,
"y": 44.14920570161545,
"width": 180.14783325004774,
"height": 53.336747638012184,
"items": [
{
"uid": "18895f59b1a_2c5a5c7a",
"locked": false,
"rotation": 0,
"type": "text",
"text": [
"abc"
],
"x": 154.37927087307924,
"y": 0,
"width": 25.768562376968507,
"height": 20.90412770669292,
"sampleTextChanged": true,
"fontSize": 15.590551181102365,
"fontFamily": "NimbusSansME",
"textBold": false,
"textItalic": false,
"textUnderline": false,
"textAlignment": "TEXT_ALIGN_LEFT",
"textLetterSpacing": 0,
"textLineSpacing": 1,
"color": {
"red": 0,
"green": 0,
"blue": 0,
"__class__": "RGBAColor",
"alpha": 1
},
"placeholderText": [
"Text"
],
"isPlaceholderTextActive": false,
"translationKey": "",
"newPathCalculation": true,
"shadow": {
"blur": 0,
"color": "{\"red\":255,\"green\":255,\"blue\":255,\"transparent\":0}",
"coords": {
"x": 0,
"y": 0
},
"distance": 0,
"opacity": 1
},
"index": 0,
"originalTextItem": [
"abc"
],
"originalXcoords": [
[
0,
8.25203001968504,
17.47085691437008,
25.768562376968507
]
]
},
{
"index": 1,
"uid": "1889607cfdf_091e59ca",
"x": 0,
"y": 32.432619931319266,
"width": 22.175427534448822,
"height": 20.90412770669292,
"items": [
{
"uid": "18895ecc7c7_2d5440b6",
"locked": false,
"rotation": 0,
"type": "text",
"text": [
"xyz"
],
"x": 0,
"y": 0,
"width": 22.175427534448822,
"height": 20.90412770669292,
"sampleTextChanged": true,
"fontSize": 15.590551181102365,
"fontFamily": "NimbusSansME",
"textBold": false,
"textItalic": false,
"textUnderline": false,
"textAlignment": "TEXT_ALIGN_LEFT",
"textLetterSpacing": 0,
"textLineSpacing": 1,
"color": {
"red": 0,
"green": 0,
"blue": 0,
"__class__": "RGBAColor",
"alpha": 1
},
"placeholderText": [
"Text"
],
"isPlaceholderTextActive": false,
"translationKey": "",
"newPathCalculation": true,
"shadow": {
"blur": 0,
"color": "{\"red\":255,\"green\":255,\"blue\":255,\"transparent\":0}",
"coords": {
"x": 0,
"y": 0
},
"distance": 0,
"opacity": 1
},
"index": 0,
"originalTextItem": [
"xyz"
],
"originalXcoords": [
[
0,
7.54406065452756,
14.95870755413386,
22.175427534448822
]
]
}
],
"type": "group",
"rotation": 0
},
{
"index": 2,
"uid": "188960e945c_35ab99fa",
"x": 44.108363106593984,
"y": 15.56765756703328,
"width": 56.72123163199389,
"height": 35.17448047647336,
"items": [
{
"uid": "18896072844_1298562b",
"locked": false,
"rotation": 0,
"type": "text",
"text": [
"group"
],
"x": 15.567657567033265,
"y": 14.270352769780445,
"width": 41.15357406496064,
"height": 20.90412770669292,
"sampleTextChanged": true,
"fontSize": 15.590551181102365,
"fontFamily": "NimbusSansME",
"textBold": false,
"textItalic": false,
"textUnderline": false,
"textAlignment": "TEXT_ALIGN_LEFT",
"textLetterSpacing": 0,
"textLineSpacing": 1,
"color": {
"red": 0,
"green": 0,
"blue": 0,
"__class__": "RGBAColor",
"alpha": 1
},
"placeholderText": [
"Text"
],
"isPlaceholderTextActive": false,
"translationKey": "",
"newPathCalculation": true,
"shadow": {
"blur": 0,
"color": "{\"red\":255,\"green\":255,\"blue\":255,\"transparent\":0}",
"coords": {
"x": 0,
"y": 0
},
"distance": 0,
"opacity": 1
},
"originalTextItem": [
"group"
],
"originalXcoords": [
[
0,
9.013287401574805,
14.342089074803152,
23.241187869094492,
31.9195220226378,
41.15357406496064
]
],
"index": 2
},
{
"index": 3,
"uid": "188960e5f49_2341c362",
"x": 0,
"y": 0,
"width": 29.803226500984252,
"height": 20.90412770669292,
"items": [
{
"uid": "188958badfe_3a73220b",
"locked": false,
"rotation": 0,
"type": "text",
"text": [
"Text"
],
"x": 0,
"y": 0,
"width": 29.803226500984255,
"height": 20.90412770669292,
"sampleTextChanged": false,
"fontSize": 15.590551181102365,
"fontFamily": "NimbusSansME",
"textBold": false,
"textItalic": false,
"textUnderline": false,
"textAlignment": "TEXT_ALIGN_LEFT",
"textLetterSpacing": 0,
"textLineSpacing": 1,
"color": {
"red": 0,
"green": 0,
"blue": 0,
"__class__": "RGBAColor",
"alpha": 1
},
"placeholderText": [
"Text"
],
"isPlaceholderTextActive": false,
"translationKey": "",
"newPathCalculation": true,
"shadow": {
"blur": 0,
"color": "{\"red\":255,\"green\":255,\"blue\":255,\"transparent\":0}",
"coords": {
"x": 0,
"y": 0
},
"distance": 0,
"opacity": 1
},
"index": 0,
"istextCircularMode": false,
"originalTextItem": [
"Text"
],
"originalXcoords": [
[
0,
9.119863435039372,
17.60027066929134,
25.1443313238189,
29.803226500984255
]
]
}
],
"type": "group",
"rotation": 0
}
],
"type": "group",
"rotation": 0
}
],
"type": "group",
"rotation": 0
}
];
const textObjects = getSpecificType(nestedData, "text");
console.log(textObjects);
/*
Output:
[
{ ... "type": "text", "text": ["abc"] ... },
{ ... "type": "text", "text": ["xyz"] ... },
{ ... "type": "text", "text": ["group"] ... }, // 注意：此处的 "group" 是 text 对象的 text 属性值，而非 type 属性
{ ... "type": "text", "text": ["Text"] ... }
]
*/注意事项与优化
类型定义与安全性
在上述代码中，我们定义了一个Item接口来增强类型安全性。在实际项目中，根据数据结构的具体情况，应该定义更精确的接口或类型，例如：
interface TextItem {
uid: string;
type: "text";
text: string[];
// ... 其他文本特有的属性
}
interface GroupItem {
uid: string;
type: "group";
items: Item[]; // items 可以包含 TextItem 或 GroupItem
// ... 其他分组特有的属性
}
type Item = TextItem | GroupItem; // 联合类型表示一个 Item 可以是 TextItem 或 GroupItem通过这样的类型定义，可以在编译阶段捕获更多潜在的错误，提高代码的健壮性。
递归方案对比
除了迭代方法，也可以使用递归来实现相同的功能。递归方案通常代码更简洁，但如前所述，可能导致栈溢出。
const getSpecificTypeRecursive = (data: Item[], targetType: string): Item[] => {
const result: Item[] = [];
const traverse = (items: Item[]) => {
for (const item of items) {
if (item.type === targetType) {
result.push(item);
}
if (item.items && item.items.length > 0) {
traverse(item.items); // 递归调用处理子项
}
}
};
traverse(data);
return result;
};
// 使用示例
const textObjectsRecursive = getSpecificTypeRecursive(nestedData, "text");
console.log(textObjectsRecursive);递归方法在逻辑上与迭代方法等效，但它通过函数调用栈来管理遍历状态。对于深度不确定的数据结构，迭代方法通常更为稳健。
性能考量
两种方法的时间复杂度都为 O(N)，其中 N 是所有嵌套层级中对象的总数，因为每个对象都会被访问一次。空间复杂度方面，迭代方法需要一个栈来存储待处理的元素，最坏情况下（例如，一个扁平的大数组），栈的大小可能接近 N。递归方法则需要调用栈来存储函数调用的上下文，最坏情况下（例如，一个深度极深的链式结构），调用栈的深度可能与嵌套深度成正比，这正是导致栈溢出的原因。因此，对于非常深的数据，迭代方法在空间效率和稳定性上更具优势。
总结
本文详细介绍了如何使用基于栈的迭代遍历方法，从复杂的嵌套对象数组中高效地提取指定
