JavaScript中嵌套对象结构中的递归树搜索 [英] Recursive tree search in a nested object structure in JavaScript
问题描述
我正在尝试找出如何以递归方式在此JSON对象中搜索节点.我已经尝试过一些东西,但无法获得它:
I'm trying to figure out how to search for a node in this JSON object recursively. I have tried something but cannot get it:
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": []
}
]
}
]
};
这是我无法使用的解决方案,可能是因为当子节点在数组中时,第一个节点只是一个值:
Here is my non-working solution, which is probably because the first node is just a value while children are in arrays:
function scan(id, tree) {
if(tree.id == id) {
return tree.label;
}
if(tree.child == 0) {
return
}
return scan(tree.child);
};
推荐答案
您的代码只是缺少一个循环,无法检查child
数组中节点的每个子节点.此递归函数将返回节点的label
属性,如果树中不存在标签,则返回undefined
:
Your code is just missing a loop to inspect each child of a node in the child
array. This recursive function will return the label
property of a node or undefined
if label not present in tree:
const search = (tree, target) => {
if (tree.id === target) {
return tree.label;
}
for (const child of tree.child) {
const res = search(child, target);
if (res) {
return res;
}
}
};
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":[]}]}]};
console.log(search(tree, 1));
console.log(search(tree, 6));
console.log(search(tree, 99));
您还可以对显式堆栈进行迭代操作,该堆栈速度更快,温度更低,并且不会导致堆栈溢出:
You can also do it iteratively with an explicit stack which is faster, cooler and won't cause a stack overflow:
const search = (tree, target) => {
const stack = [tree];
while (stack.length) {
const curr = stack.pop();
if (curr.id === target) {
return curr.label;
}
stack.push(...curr.child);
}
};
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":[]}]}]};
for (let i = 0; ++i < 12; console.log(search(tree, i)));
这篇关于JavaScript中嵌套对象结构中的递归树搜索的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!