Javascript递归树搜索 [英] Javascript recursive tree search

问题描述

试图弄清楚如何递归搜索此JSON对象中的节点。我尝试了一些但却无法得到它：

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": []
                }
            ]
        }
    ]
};

我的工作解决方案不正常，可能是因为第一个节点只是一个值，而子节点是数组：

My not working solution, 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);
};

推荐答案

您的代码缺少检查每个孩子的循环子数组中的节点。如果树中没有标签，则此递归函数将返回节点的标签属性或 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屋！