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 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):

You can also do it iteratively with an explicit stack which won't cause a stack overflow (but note that the shorthand stack.push(...curr.child); can overflow the argument size for some JS engines due to the spread syntax, so use an explicit loop or concat for massive child arrays):

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 属性(如果他们愿意)，或者以其他方式使用对象.

A somewhat more generic design would return the node itself and let the caller access the .label property if they want to, or use the object in some other manner.

请注意，JSON 纯粹是用于序列化(字符串化、原始)数据的字符串格式.一旦您将 JSON 反序列化为 JavaScript 对象结构，就像这里一样，它就不再是 JSON.

Note that JSON is purely a string format for serialized (stringified, raw) data. Once you've deserialized JSON into a JavaScript object structure, as is here, it's no longer JSON.

这篇关于JavaScript 嵌套对象结构中的递归树搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！