Как адаптировать итеративный алгоритм обхода бинарного дерева к обходу сильноветвящегося дерева?

Question

[Leo_Eldorado]

Здравствуйте.
Мне необходимо реализовать итеративный обход сильноветвящегося дерева в глубину, в порядке "вершина – левое поддерево – правое поддерево". Как сделать это для бинарного дерева, используя стек, понятно, но как сделать для сильноветвящегося не очень ясно. Прошу ссылку на литературу или на реализацию на любом языке.

Answer 1

[Сергей Соловьев]

Разницы нет. Просто теперь потомки каждого узла лучше представлять в виде массива, по которому нужно итерироваться - без left и right

void Visit(Node node) {
     for (auto child: node.children()) {
           stack.append(child);
     // Не так
     // if (node.left != nullptr) {
     //    stack.append(node.left);
     //  }
     // if (node.right != nullptr) {
     //    stack.append(node.right);
     //  }
   
}

Comments

[Leo_Eldorado]

А этот пример ни для обхода ли в ширину, а не в глубину?

Answer 2

[0xD34F]

на любом языке

Ну как скажете:

копирование
суммирование
поиск значений, удовлетворяющих какому-либо условию - одного или всех, что есть

Answer 3

[Wataru]

Вам надо помнить, сколько детей каждой вершины вы уже обработали. Поэтому в стеке надо хранить 2 числа: вершину и сколько детей обработали. Или 2 стека параллельно обновлять.

Изначально в стек поместите корень дерева и 0. Потом в цикле, пока стек не пуст, смотрите на вершину стека. Если там счетчик 0, то выводите вершину в ответ. Увеличивайте там счетчик на 1. Если он стал равен количеству детей у вершины, удаляйте ее из стека. Иначе добавляйте в стек вершину-ребенка с номером из счетчика с 0. Можно чуть по другому: выводите вершину при помещении ее в стек с 0. Но тогда надо отдельно вывести корень дерева.