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