Как найти путь поиска узла в дереве JS / TS

Question

У меня есть объект, который представляет дерево.

Я хочу найти узел и его путь поиска. Для поиска узла я создал функцию, которая отлично работает, вот код

let treeData = {
  id: 1,
  name: "Node 1",
  child: [{
      id: 2,
      name: "Node 2",
      child: [{
          id: 3,
          name: "Node 3"
        },
        {
          id: 4,
          name: "Node 4",
          child: [{
            id: 10,
            name: "Node 10"
          }]
        }
      ]
    },
    {
      id: 5,
      name: "Node 5",
      child: [{
        id: 6,
        name: "Node 6"
      }]
    }
  ]
};


function _searchTree(nodeId, parent) {
  const stack = [parent];
  while (stack.length) {
    const node = stack.pop();
    if (node.id === nodeId) {
      return node;
    }
    if (node.child) {
      stack.push(...node.child);
    }

  }
  return stack.pop() || null;
}
const _node = _searchTree(10, treeData);

console.log("Found node", _node);

Эта функция может найти узел дерева на основе переданного идентификатора. Но как я могу найти путь поиска предмета? Функция обеспечила основание стека, ответ с рекурсией также приемлем.

Answer 1

Вы можете поместить в стек как узел, так и текущий путь, а затем действовать соответственно. Я предполагаю, что элемент пути является индексом в массиве child.

Вот как это будет выглядеть:

function _searchTree(nodeId, parent) {
    const stack = [[parent, []]];
    while (stack.length) {
       const [node, path] = stack.pop();
       if (node.id === nodeId) {
          return path;
       }
       if (node.child) {
           stack.push(...node.child.map((node, i) => [node, [...path, i]]));
       }
    }
}

const a = {id: 1,name: "Node 1",child: [{id: 2,name: "Node 2",child: [{id: 3,name: "Node 3"},{id: 4,name: "Node 4",child: [{ id: 10, name: "Node 10" }]}]},{id: 5,name: "Node 5",child: [{id: 6,name: "Node 6"}]}]};
const path = _searchTree(6, a);
console.log(path); // [1, 0]

Обратите внимание, что в исходном коде также есть два исправления:

• Финальный return stack.pop() || null; может быть просто return null, потому что stack пуст в этой точке. Если undefined ОК в качестве возвращаемого значения, вы можете опустить всю строку.

• Перед итерацией node.child необходимо убедиться, что свойство существует.