Обход постзаказа == обход снизу вверх и обход предзаказа == обход сверху вниз?

Question

Было бы правильно сказать, что обход дерева после заказа должен использоваться для выполнения обхода снизу вверх, тогда как обход перед порядком должен использоваться для обхода двоичного дерева сверху вниз?

Это было верно во всех примерах, с которыми я встречался, поэтому я просто хотел подтвердить. Есть некоторые проблемы, для которых интуитивно понятно начать с листьев (внизу). Можем ли мы использовать обход пост-заказа для их решения (и наоборот)?

Спасибо!

Answer 1

Нет. Хотя post-order traversal и pre-order traversal имеют четкое определение, термины bottom-up traversal или top-down traversal могут интерпретироваться по-разному, они обычно не принимаются для двоичных деревьев. Если кто-то использует последние термины для обозначения деревьев, точное значение зависит от контекста.

Посмотрите на картинку из wiki :

Does pre-order traversal here look like top-down traversal? Or post-order likes bottom-up traversal? Seems no.

Perhaps you want to consider BFS methods to get порядок уровней

Answer 2

Нет. И на самом деле термины снизу вверх / сверху вниз обычно используются для графа, но для деревьев они используются, как описано ниже:

• Предварительный обход: Родители посещаются перед посещением детей, а братьев и сестер посещают в порядке слева направо (может быть последовательно, но не всегда).
• Последовательный обход: Дети посещаются до посещения родителей, братьев и сестер в порядке слева направо.
• Обход сверху вниз: узлы посещаются в порядке неубывающей глубины. Это в основном обход по уровням
• Обход снизу вверх: Это в точности обратное обходу сверху вниз