программирование 1783/20

Тема 1 Двоичные деревья
Вариант 9
Задание.
Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска:
- поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа;
- добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений;
- построчный вывод дерева в наглядном виде на основе процедур обхода:
    - в прямом порядке;
    - с помощью обратно-симметричного обхода;

Рекомендации:
1. Объявить и реализовать подпрограмму поиска.
Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением.
При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа.
При несовпадении поиск продолжается в левом или правом поддереве текущей вершины.
2. Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево.
Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины.
Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей.
В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева.
При совпадении ключей надо просто увеличить значение счетчика появлений.
3. Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и обратно-симметричном порядке:
Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д.
Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины.
Все процедуры обхода имеют похожую структуру.
Например, процедура обхода в прямом направлении должна:
- проверить пустоту очередного поддерева;
- вывести в цикле необходимое число пробелов в соответствии с уровнем вершины;
- вывести информационную часть текущей вершины;
- вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1;
- вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1.

Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице.
Главная программа должна предоставлять следующие возможности:
- создание дерева с заданным числом вершин со случайными ключами;
- добавление в дерево одной вершины с заданным пользователем значением ключа;
- поиск в дереве вершины с заданным ключом;
- построчный вывод дерева в наглядном виде.