Примеры обхода дерева до / после заказа в реальном мире
Я прекрасно понимаю алгоритмы обхода дерева до, в порядке и после заказа. ( Ссылка). Я понимаю несколько применений: по порядку обхода двоичных деревьев поиска по порядку, предзаказ по клонированию дерева. Но я не могу на всю жизнь придумать реальную задачу, для выполнения которой мне понадобится обход после заказа.
Можете ли вы дать мне пример? И: можете ли вы дать мне лучшее использование для обхода предварительного заказа?
Изменить: Кто-нибудь может дать мне пример, кроме деревьев выражений и RPN? Это действительно все, что нужно после заказа?
3 ответа
Топологическая сортировка - это пост-порядок обхода деревьев (или направленных ациклических графов).
Идея состоит в том, что узлы графа представляют задачи и ребро от A в B указывает на то, что A должен быть выполнен до B, Топологическая сортировка организует эти задачи в такой последовательности, чтобы все зависимости задачи появлялись раньше, чем сама задача. Любая система сборки, такая как UNIX make, должна реализовывать этот алгоритм.
Пример, упомянутый Дарио - уничтожение всех узлов дерева с ручным управлением памятью - является примером этой проблемы. В конце концов, задача уничтожения узла зависит от уничтожения его потомков.
Почтовый заказ (может быть) используется компиляторами. Рассмотрим дерево выражений для a + b + c, машинный язык потребует такой последовательности a b + c +, Это также называется обратной польской нотацией (RPN). На странице Википедии написано: "РПН, он же Postfix"
Пост-заказ также необходим для уничтожения дерева, так же, как предварительный заказ необходим для его создания / клонирования.
Как отметил Хенк Холтерман, уничтожение дерева с помощью ручного управления памятью обычно является обходом после заказа.
псевдокод:
destroy(node) {
if (node == null) return;
destroy(node.left)
destroy(node.right)
// Post-order freeing of current node
free(node)
}