JavaScript中嵌套对象结构中的递归树搜索
JavaScript中嵌套对象结构中的递归树搜索
提问于 2018-08-29 05:25:46
我正在尝试弄清楚如何递归地搜索这个JSON对象中的节点。我已经尝试了一些东西，但无法获得它：
var tree = {
"id": 1,
"label": "A",
"child": [
{
"id": 2,
"label": "B",
"child": [
{
"id": 5,
"label": "E",
"child": []
},
{
"id": 6,
"label": "F",
"child": []
},
{
"id": 7,
"label": "G",
"child": []
}
]
},
{
"id": 3,
"label": "C",
"child": []
},
{
"id": 4,
"label": "D",
"child": [
{
"id": 8,
"label": "H",
"child": []
},
{
"id": 9,
"label": "I",
"child": []
}
]
}
]
};下面是我的不起作用的解决方案，可能是因为第一个节点只是一个值，而子节点在数组中：
function scan(id, tree) {
if(tree.id == id) {
return tree.label;
}
if(tree.child == 0) {
return
}
return scan(tree.child);
};回答 2
Stack Overflow用户
回答已采纳
发布于 2018-08-29 05:36:52
您的代码缺少一个用于检查child数组中每个节点的子节点的循环。如果树中不存在标签，此递归函数将返回节点或undefined的label属性：
const search = (tree, target) => {
if (tree.id === target) {
return tree.label;
}
for (const child of tree.child) {
const found = search(child, target);
if (found) {
return found;
}
}
};
const tree = {"id":1,"label":"A","child":[{"id":2,"label":"B","child":[{"id":5,"label":"E","child":[]},{"id":6,"label":"F","child":[]},{"id":7,"label":"G","child":[]}]},{"id":3,"label":"C","child":[]},{"id":4,"label":"D","child":[{"id":8,"label":"H","child":[]},{"id":9,"label":"I","child":[]}]}]};
console.log(search(tree, 1));
console.log(search(tree, 6));
console.log(search(tree, 99));
您也可以使用显式堆栈迭代地执行此操作，这不会导致堆栈溢出(但请注意，由于扩展语法，速记stack.push(...curr.child);可能会溢出某些JS引擎的参数大小，因此对于大量子数组，请使用显式循环或concat )：
const search = (tree, target) => {
for (const stack = [tree]; stack.length;) {
const curr = stack.pop();
if (curr.id === target) {
return curr.label;
}
stack.push(...curr.child);
}
};
const tree = {"id":1,"label":"A","child":[{"id":2,"label":"B","child":[{"id":5,"label":"E","child":[]},{"id":6,"label":"F","child":[]},{"id":7,"label":"G","child":[]}]},{"id":3,"label":"C","child":[]},{"id":4,"label":"D","child":[{"id":8,"label":"H","child":[]},{"id":9,"label":"I","child":[]}]}]};
for (let i = 0; ++i < 12; console.log(search(tree, i)));
一种更通用的设计是返回节点本身，并允许调用者访问.label属性，或者以其他方式使用对象。
请注意，JSON纯粹是序列化(stringified，原始)数据的字符串格式。一旦将JSON反序列化为JavaScript对象结构，它就不再是JSON了。
Stack Overflow用户
发布于 2018-08-30 02:49:49
可以使用第三个参数递归编写scan，该参数对要扫描的节点队列进行建模
const scan = (id, tree = {}, queue = [ tree ]) =>
// if id matches node id, return node label
id === tree.id
? tree.label
// base case: queue is empty
// id was not found, return false
: queue.length === 0
? false
// inductive case: at least one node
// recur on next tree node, append node children to queue
: scan (id, queue[0], queue.slice(1).concat(queue[0].child))因为JavaScript支持默认参数，所以scan的调用点是不变的
console.log
( scan (1, tree) // "A"
, scan (3, tree) // "C"
, scan (9, tree) // "I"
, scan (99, tree) // false
)在下面的浏览器中验证它是否正常工作
const scan = (id, tree = {}, queue = [ tree ]) =>
id === tree.id
? tree.label
: queue.length === 0
? false
: scan (id, queue[0], queue.slice(1).concat(queue[0].child))
const tree =
{ id: 1
, label: "A"
, child:
[ { id: 2
, label: "B"
, child:
[ { id: 5
, label: "E"
, child: []
}
, { id: 6
, label: "F"
, child: []
}
, { id: 7
, label: "G"
, child: []
}
]
}
, { id: 3
, label: "C"
, child: []
}
, { id: 4
, label: "D"
, child:
[ { id: 8
, label: "H"
, child: []
}
, { id: 9
, label: "I"
, child: []
}
]
}
]
}
console.log
( scan (1, tree) // "A"
, scan (3, tree) // "C"
, scan (9, tree) // "I"
, scan (99, tree) // false
)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52066403
复制相关文章
相似问题