Примеры обхода дерева до/после заказа

Question

Я понимаю, что алгоритмы обхода дерева по порядку, по порядку и по порядку просто отлично. (Reference). Я понимаю несколько применений: в порядке для перемещения двоичных деревьев поиска по порядку, предварительный порядок клонирования дерева. Но я не могу для жизни меня придумать реальную задачу мира, для которой мне понадобится пост-ордер.

Можете ли вы привести мне пример? И: можете ли вы лучше использовать меня для предварительного обхода?

Редактировать: Может ли кто-нибудь дать мне пример, кроме деревьев выражений и RPN? Неужели это действительно все пост-порядок?

Answer 1

Topological sorting это пост-порядок обхода деревьев (или ориентированных ациклических графов).

Идея заключается в том, что узлы графа представляют задачи и ребро из A к B указывает на то, что A должен быть выполнен перед B. Топологическая сортировка организует эти задачи в последовательности, так что все зависимости задачи появляются раньше самой задачи. Любая система построения, такая как UNIX make, должна реализовать этот алгоритм.

Пример, который Дарио упомянул - уничтожение всех узлов дерева с ручным управлением памятью - пример этой проблемы. В конце концов, задача уничтожения узла зависит от разрушения его детей.

Answer 2

Почтовый заказ (может быть) использован компиляторами. Рассмотрим дерево выражений для a + b + c, для машинного языка потребуется последовательность, например a b + c +. Это также называется Reverse polish Notation (RPN). На странице Википедии в нем написано: «RPN aka Postfix»

Post-order также требуется для уничтожения дерева, так же как и предварительный заказ для создания/клонирования.

Answer 3

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

Псевдокод:

destroy(node) { 
    if (node == null) return; 

    destroy(node.left) 
    destroy(node.right) 

    // Post-order freeing of current node 
    free(node) 
}