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

#cpp #c #алгоритм #бинарное_дерево

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

Ответы

Ответ 1

Т.к. рекурсию использовать нельзя, мы вместо неё будем использовать два стэка. Вот
весь алгоритм, в результате его будут распечатаны все вершины бинарного дерева в post-order
порядке (можно вместо распечатки делать какое-то полезное действие):


Добавить корень в первый стэк.
Пока первый стэк не пуст выполнять следующие два подпункта:

2.1. Извлечь узел из вершины первого стэка, добавить его во второй стэк.

2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк.
Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка
и печатать.


Замечание: в конце порядок распечатки для поддеревьев будет тот же что и при помещении
в 1й стэк, т.е. мы помещали в 1й стэк левого а затем правого ребёнка, при распечатке
в итоге будет раньше распечатано левое поддерево, затем правое, а затем родитель. Если
нужно в распечатке иметь вначале правое поддерево а затем левое тогда нужно в 1й стэк
помещать вначале правого ребёнка затем левого.