Здравствуйте, как на с/с++ написать нерекурсивный обход бинарного дерева через стек методом post-order (сначала листья, потом корень)?
-
Использовать свои собственные знания. Если не получится, поможем. – HasmikGaryaka 22 окт '17 в 16:00
1 ответ
Т.к. рекурсию использовать нельзя, мы вместо неё будем использовать два стэка. Вот весь алгоритм, в результате его будут распечатаны все вершины бинарного дерева в post-order порядке (можно вместо распечатки делать какое-то полезное действие):
Добавить корень в первый стэк.
Пока первый стэк не пуст выполнять следующие два подпункта:
2.1. Извлечь узел из вершины первого стэка, добавить его во второй стэк.
2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк.
Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка и печатать.
Замечание: в конце порядок распечатки для поддеревьев будет тот же что и при помещении в 1й стэк, т.е. мы помещали в 1й стэк левого а затем правого ребёнка, при распечатке в итоге будет раньше распечатано левое поддерево, затем правое, а затем родитель. Если нужно в распечатке иметь вначале правое поддерево а затем левое тогда нужно в 1й стэк помещать вначале правого ребёнка затем левого.
-
Может стоит дополнительно пояснить, что порядок печати поддеревьев обратен порядку их помещения в первый стек в цикле 2. Т.е. если надо печатать сначала левое, потом правое, то в стек надо класть сначала правое, а сразу потом левое. – avp 22 окт '17 в 17:57
-
@avp Как раз таки вершины будут распечатаны в том же порядке как помещались в первый стэк, если в 1й стэк помещали левый а потом правый, то в конце будут распечатаны тоже вначале левое поддерево а потом правое. Допустим мы в 1й стэк поместили левое потом правое, значит на обработку вначале извлечётся правое, а это значит что правое поместится во второй стэк раньше, и только затем во всторой стэк поместится левое поддерево, значит при распечатке из стэка 2го вначале извлекётся левое поддерево (т.к. оно ближе к вершине стэка), а только потом правое. – Arty 22 окт '17 в 18:08
-
-