Примеры обратного пересечения дерева в реальном мире

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

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

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

Ответы

Ответ 1

Топологическая сортировка - это последующий обход деревьев (или направленных ациклических графов).

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

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

Ответ 2

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

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

Ответ 3

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

псевдокод:

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

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

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