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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

псевдокод:

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

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

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