4

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

1
  • Использовать свои собственные знания. Если не получится, поможем. 22 окт 2017 в 16:00

1 ответ 1

3

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

  1. Добавить корень в первый стэк.

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

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

    2.2. Добавить левого затем правого ребёнка узла из п. 2.1 в первый стэк.

  3. Распечатать содержимое второго стэка, т.е. в цикле извлекать вершину второго стэка и печатать.

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

4
  • Может стоит дополнительно пояснить, что порядок печати поддеревьев обратен порядку их помещения в первый стек в цикле 2. Т.е. если надо печатать сначала левое, потом правое, то в стек надо класть сначала правое, а сразу потом левое.
    – avp
    22 окт 2017 в 17:57
  • @avp Как раз таки вершины будут распечатаны в том же порядке как помещались в первый стэк, если в 1й стэк помещали левый а потом правый, то в конце будут распечатаны тоже вначале левое поддерево а потом правое. Допустим мы в 1й стэк поместили левое потом правое, значит на обработку вначале извлечётся правое, а это значит что правое поместится во второй стэк раньше, и только затем во всторой стэк поместится левое поддерево, значит при распечатке из стэка 2го вначале извлекётся левое поддерево (т.к. оно ближе к вершине стэка), а только потом правое.
    – Arty
    22 окт 2017 в 18:08
  • Точно, не учел операций со стеком 2.
    – avp
    22 окт 2017 в 19:31
  • Большое спасибо) 26 окт 2017 в 6:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.