Деревья
Восходящий порядок (post-order) обхода вызывает операцию для данной вершины после просмотра вершин-детей:
Восходящий порядок применяется, когда операция для вершины зависит от поддеревьев. Примерами служат вычисление высоты дерева (взять максимум из высот двух поддеревьев и добавить единицу), обработка дерева в графическом пакете (выделить место на странице для каждого поддерева и объединить их в области для данной вершины), а также вычисление общего занимаемого места.
Нисходящий порядок (pre-order) используется редко, так что мы не будем его рассматривать.
На самом деле деревья двоичного поиска применяются редко, хотя В-деревья, обычно сильно разветвленные, используются для хранения информации на внешних носителях. В каждодневном программировании деревья часто используются для представления структур действий и выражений. Например, действие:
mid = (low + high) / 2;
Может быть представлено в виде дерева синтаксического разбора (parse tree), показанного на рисунке ниже. Для вычисления значения дерева нужно обойти его в восходящем порядке и выполнить в каждой вершине соответствующее действие.
Более детально мы будем рассматривать деревья синтаксического разбора в главе 9.
Упражнение 2.11
Сравните быстродействие lookup и nrlookup. Насколько рекурсия медленнее итеративной версии?
Упражнение 2.12
Используйте фланговый обход для создания процедуры сортировки. Какова ее временная сложность? При каких условиях она может работать медленно? Как ее производительность соотносится с нашей процедурой quicksort и с библиотечной версией?
Упражнение 2.13
Придумайте и реализуйте набор тестов, удостоверяющих, что процедуры работы с деревьями корректны.