Прохождение бинарного дерева (post-order)

Здравствуйте, как на с/с++ написать нерекурсивный обход бинарного дерева через стек методом post-order (сначала листья, потом корень)?

Ответ

Т.к. рекурсию использовать нельзя, мы вместо неё будем использовать два стэка. Вот весь алгоритм, в результате его будут распечатаны все вершины бинарного дерева в post-order порядке (можно вместо распечатки делать какое-то полезное действие):
Добавить корень в первый стэк. Пока первый стэк не пуст выполнять следующие два подпункта:
2.1. Извлечь узел из вершины первого стэка, добавить его во второй стэк.
2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк. Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка и печатать.
Замечание: в конце порядок распечатки для поддеревьев будет тот же что и при помещении в 1й стэк, т.е. мы помещали в 1й стэк левого а затем правого ребёнка, при распечатке в итоге будет раньше распечатано левое поддерево, затем правое, а затем родитель. Если нужно в распечатке иметь вначале правое поддерево а затем левое тогда нужно в 1й стэк помещать вначале правого ребёнка затем левого.