Рекурсивный поиск по дереву в структуре вложенных объектов в 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

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
  )

Связанный рекурсивный поиск с использованием функций высшего порядка

Answer 2

В вашем коде отсутствует цикл для проверки каждого дочернего узла в массиве 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)));