Для данного массива родительских узлов распечатать предварительный обход дерева

Дан несортированный массив узлов, в котором узел определяется как:
Node { int id; int parent_id; string label; }

У каждого узла есть свой уникальный идентификатор. parent_id определить своего родителя в дереве. Вопрос в том, как сделать предварительный обход дерева? (не обязательно двоичное дерево)

Это вопрос интервью, который беспокоил меня несколько дней. Что я могу придумать, так это использовать хеш-карту map<int,list<node> >, где ключ - это родительский элемент. Тогда я не могу идти дальше. Должен ли я построить дерево с карты и выполнить обход перед заказом или есть хороший способ сделать это прямо с карты? Тогда как? Любая подсказка приветствуется!


data-structures tree preorder
person user1941469    schedule 01.01.2013    source источник
comment
Есть ли что-нибудь, что определяет порядок детей? Вы можете пометить корневой узел при построении карты, а затем просто пройти по этой карте в предварительном порядке, начиная с корня.   -  person Faruk Sahin    schedule 02.01.2013

Ответы (1)


arrow_upward
1
arrow_downward

Итак, вам нужно:

map<int, list<Node> > childMap;
map<int, Node> nodeMap;

Вы найдете узел, у которого нет родителя (parent_id = -1 или что-то в этом роде), это, очевидно, корень. Вы вызываете функцию ниже для этого узла после настройки карт выше.

preOrder(int id)
{
  process(nodeMap[id]);
  foreach (Node node: childMap[id])
    preOrder(node);
}
person Bernhard Barker    schedule 01.01.2013
comment
Отличный ответ. Достаточно DFS. - person user1941469; 02.01.2013