本教程详细介绍了如何使用迭代式深度优先搜索（dfs）算法，从复杂的深度嵌套对象数组中高效地提取所有具有特定`type`属性的对象。通过维护一个栈来管理待处理的元素，该方法能够避免递归带来的潜在堆栈溢出风险，并提供清晰、可控的遍历过程，适用于处理结构化数据中特定类型元素的筛选需求。
在处理复杂的数据结构时，我们经常会遇到需要从一个深度嵌套的对象数组中，根据某个属性（例如 type）的值来筛选出所有符合条件的元素。这些嵌套结构可能包含多层 items 数组，使得简单的扁平化或单层循环无法满足需求。本文将介绍一种健壮且高效的迭代式深度优先搜索（DFS）方法来解决此类问题。
场景示例
假设我们有一个包含多层嵌套对象的数组，每个对象可能包含一个 type 属性和一个 items 数组，items 数组中又可能包含更多类似结构的对象。我们的目标是找出所有 type 属性值为 “text” 的对象，无论它们嵌套在哪个层级。
以下是一个简化后的示例数据结构：
[ { "index": 3, "type": "group", "items": [ { "type": "text", "text": ["abc"] }, { "type": "group", "items": [ { "type": "text", "text": ["xyz"] } ] } ] } ]
核心思想：迭代式深度优先搜索
为了遍历所有嵌套层级并找到目标对象，我们可以采用深度优先搜索（DFS）策略。由于递归式 DFS 在处理极深嵌套时可能导致栈溢出，我们推荐使用迭代式 DFS，它通过显式地维护一个栈来管理待访问的节点。
算法步骤
- 初始化结果数组和工作栈： 创建一个空数组用于存储符合条件的对象，并创建一个栈，将初始的顶层元素全部推入栈中。
- 循环遍历栈： 只要栈不为空，就持续执行以下操作：
- 弹出当前元素： 从栈顶弹出一个元素作为当前处理对象。
- 类型检查： 检查当前对象的 type 属性是否与目标类型匹配。如果匹配，则将其添加到结果数组中。
- 处理子元素： 如果当前对象包含 items 数组（即子元素），则将这些子元素全部推入栈中。这样可以确保在处理完当前节点的兄弟节点之前，优先处理其所有子节点，从而实现深度优先的遍历。
- 返回结果： 当栈为空时，所有可访问的元素都已检查完毕，返回结果数组。
实现示例 (typescript)
以下是使用 TypeScript 实现上述算法的示例代码：
/** * 从深度嵌套的对象数组中，根据指定的类型提取所有匹配的对象。 * * @param data 原始的深度嵌套对象数组。 * @param targetType 目标对象的类型字符串。 * @returns 包含所有匹配类型对象的数组。 */ const getSpecificType = (data: Record<String, any>[], targetType: string): Record<string, any>[] => { const result: Record<string, any>[] = []; // 存储符合条件的结果 // 使用扩展运算符将初始数据扁平化并作为栈的初始内容 // 确保栈中每个元素都是一个对象，以便后续处理 const stack: Record<string, any>[] = [...data]; while (stack.length > 0) { // 从栈顶弹出一个元素进行处理 const current = stack.pop(); // 确保弹出的元素有效，避免处理 undefined 或 null if (!current) { continue; } // 检查当前元素的类型是否符合目标类型 if (current.type === targetType) { result.push(current); // 如果匹配，加入结果数组 } // 如果当前元素有 'items' 属性且它是一个数组， // 则将其所有子元素推入栈中，以便后续遍历 if (Array.isArray(current.items)) { // 使用扩展运算符将所有子元素推入栈中 // 注意：这里是 push 而不是 unshift，因为 pop 总是从数组末尾取出， // push 也是向数组末尾添加，这样可以保持 DFS 的正确性。 stack.push(...current.items); } } return result; }; // 示例数据（与问题内容相同） const nestedData = [ { "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); /* 预期输出 (简化版，包含关键属性) [ { "uid": "18895f59b1a_2c5a5c7a", "type": "text", "text": ["abc"] }, { "uid": "18895ecc7c7_2d5440b6", "type": "text", "text": ["xyz"] }, { "uid": "18896072844_1298562b", "type": "text", "text": ["group"] }, // 注意这里虽然是"group"但type是"text" { "uid": "188958badfe_3a73220b", "type": "text", "text": ["Text"] } ] */
注意事项与总结
-
类型安全性： 上述示例中使用了 Record<string, any>[] 作为通用类型，这在处理结构不完全确定的 jsON 数据时非常灵活。然而，在实际项目中，如果数据结构已知，强烈建议定义更具体的接口（Interface）或类型（Type），以增强代码的类型安全性、可读性和可维护性。例如，可以定义 Item 接口，其中 items 属性为 Item[]，实现更严格的类型检查。
-
性能考量： 这种迭代式 DFS 方法的时间复杂度为 O(N)，其中 N 是数据结构中所有节点的总数，因为它每个节点只访问一次。空间复杂度在最坏情况下（例如一个非常扁平但宽度很大的树，或者一个非常深的链式结构）也是 O(D)，其中 D 是最大深度或最大宽度，取决于栈中存储的元素数量，这与递归方法类似，但避免了 javaScript 调用栈的限制。
-
递归替代方案： 虽然迭代法避免了栈溢出，但递归方法在某些情况下可能提供更简洁的语法。如果嵌套深度已知且不深，或者您确信不会遇到栈溢出问题，递归方法也是一个可行的选择。例如：
const getSpecificTypeRecursive = (data: Record<string, any>[], targetType: string): Record<string, any>[] => { let result: Record<string, any>[] = []; data.forEach(item => { if (item.type === targetType) { result.push(item); } if (Array.isArray(item.items)) { result = result.concat(getSpecificTypeRecursive(item.items, targetType)); } }); return result; };然而，对于不确定的深度，迭代式方法通常更为稳健。
通过本文介绍的迭代式深度优先搜索方法，您可以有效地从任何深度嵌套的对象数组中提取符合特定条件的元素，为复杂数据处理提供了可靠的解决方案。