2015-05-13
704
 |
 |
Пример 1. Рассмотрим результаты просмотра для приведенных алгоритмов, при условии, что обработка корневого элемента сводится к выводу значения его информационного поля, а дерево в этот момент имеет следующие узлы:
Результаты просмотра:
| Алгоритм «Слева направо» | 1, 3, 7, 10, 70, 96, 98 |
| Алгоритм «Справа налево» | 98, 96, 70, 10, 7, 3, 1 |
| Алгоритм «Сверху вниз» | 10, 3, 1, 7, 96, 70, 98 |
Из приведенной таблицы видно, что, просто изменяя порядок просмотра дерева (слева-направо и справа-налево), можно получить отсортированные по возрастанию или по убыванию числа.
Пример 2. Пусть в узлах дерева расположены элементы арифметического выражения:
 |
Результаты просмотра:
| «Слева направо» | 8 * 7 + 9 – 4 | инфиксная форма записи выражения |
| «Сверху вниз» | + * 8 7 – 9 4 | префиксная форма записи выражения |
| «Снизу вверх» | 8 7 * 9 4 – + | постфиксная форма записи выражения |
A5. Поиск элемента в двоичном упорядоченном дереве
Вывод. Тексты приведенных алгоритмов очень компактны и просты в понимании.
В заключение отметим, что рекурсивные алгоритмы широко используются в базах данных и при построении компиляторов, в частности для проверки правильности записи арифметических выражений, синтаксис которых задается с помощью синтаксических диаграмм.
Для закрепления материала предлагается решить следующую задачу:
Данные о студентах содержат фамилию и три оценки, полученные на экзаменах. Занести их с клавиатуры или из текстового файла в бинарное дерево поиска, упорядоченное по значению средней оценки. Затем вывести на экран список студентов, упорядоченный по убыванию средней оценки. Кроме фамилий вывести все три оценки и их среднее значение с точностью до одного знака после запятой.
