Иллюстрированный самоучитель по практике программирования

Деревья

Восходящий порядок (post-order) обхода вызывает операцию для данной вершины после просмотра вершин-детей:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Деревья

Восходящий порядок применяется, когда операция для вершины зависит от поддеревьев. Примерами служат вычисление высоты дерева (взять максимум из высот двух поддеревьев и добавить единицу), обработка дерева в графическом пакете (выделить место на странице для каждого поддерева и объединить их в области для данной вершины), а также вычисление общего занимаемого места.

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

На самом деле деревья двоичного поиска применяются редко, хотя В-деревья, обычно сильно разветвленные, используются для хранения информации на внешних носителях. В каждодневном программировании деревья часто используются для представления структур действий и выражений. Например, действие:

mid = (low + high) / 2;

Может быть представлено в виде дерева синтаксического разбора (parse tree), показанного на рисунке ниже. Для вычисления значения дерева нужно обойти его в восходящем порядке и выполнить в каждой вершине соответствующее действие.

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Деревья

Более детально мы будем рассматривать деревья синтаксического разбора в главе 9.

Упражнение 2.11
Сравните быстродействие lookup и nrlookup. Насколько рекурсия медленнее итеративной версии?

Упражнение 2.12
Используйте фланговый обход для создания процедуры сортировки. Какова ее временная сложность? При каких условиях она может работать медленно? Как ее производительность соотносится с нашей процедурой quicksort и с библиотечной версией?

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

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.