JavaScript中嵌套对象结构中的递归树搜索

Question

我试图找出如何递归地在此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);
};

Answer 1

您的代码只是缺少一个循环来检查child数组中节点的每个子节点。此递归函数将返回label节点的属性，或者undefined如果树中不存在标签，则返回该属性：

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

您还可以使用显式堆栈进行迭代，该堆栈更快，更凉爽并且不会导致堆栈溢出：

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