Лабораторная работа № 7.
Бинарное дерево

1. Постановка задачи

Разработать модуль для работы с бинарным деревом. Модуль должен обеспечивать следующие возможности работы с деревом:

добавление корневой вершины дерева;
добавление левой подвершины;
добавление правой подвершины;
поиск вершины, содержащей определённую информацию;
удаление листа дерева.

На основе базовых операций с деревом необходимо разработать следующие подпрограммы:

ввод элементов бинарного дерева из файла;
вывод элементов бинарного дерева на экран;
удаление вершины и всех её подвершин;
определение количества вершин дерева, удовлетворяющих условию.

Разработать программу, к которой будет подключаться разработанный модуль. Программа должна сделать следующее:

ввести дерево из файла;
добавить к дереву несколько вершин (сначала ищем нужную вершину, затем добавляем к ней подвершину);
удалить из дерева несколько вершин (сначала ищем нужную вершину, затем удаляем её);
найти количество элементов дерева, удовлетворяющих условию.

После каждого изменения выводить содержимое дерева.

Имена файлов передаются через параметры программы.

Создать бинарное дерево из целых чисел в диапазоне -20 до +60. Найти в дереве количество элементов, кратных 5.

2. Таблица данных

2.1. Добавление корневой вершины дерева

Класс	Имя	Смысл	Тип	Структура
Входные данные	info	Информация для вставки в корневую вершину	TInfo	простая переменная
Выходные данные	root	Указатель на корневую вершину дерева	указатель	простая переменная

2.2. Добавление левой подвершины/Добавление правой подвершины

Класс	Имя	Смысл	Тип	Структура
Входные данные	node	Указатель на вершину, к которой надо добавить подвершину	указатель	простая переменная
Входные данные	info	Информация для вставки в подвершину	TInfo	простая переменная
Выходные данные	f	Результат добавления (нельзя добавить, если подвершина уже есть)	boolean	простая переменная

2.3. Поиск вершины, содержащей определённую информацию

Класс	Имя	Смысл	Тип	Структура
Входные данные	info	Информация для поиска	TInfo	простая переменная
Выходные данные	node	Указатель на найденную вершину (nil, если вершина не найдена)	указатель	простая переменная

2.4. Ввод элементов дерева из текстового файла

Класс	Имя	Смысл	Тип	Структура
Входные данные	name	Имя файла	строка	простая переменная
Выходные данные	root	Указатель на корневую вершину дерева	указатель	простая переменная

2.5. Вывод элементов дерева на экран

Класс	Имя	Смысл	Тип	Структура
Входные данные	root	Указатель на корневую вершину дерева	указатель	простая переменная

2.6. Определение количества вершин дерева, удовлетворяющих условию

Класс	Имя	Смысл	Тип	Структура
Входные данные	root	Указатель на корневую вершину дерева	указатель	простая переменная
Выходные данные	k	Количество вершин дерева, удовлетворяющих условию	цел.	простая переменная

3. Аномалии

Недостаточно параметров.
Невозможно открыть файл для чтения.
Некорректные данные в файле.
Значения в текстовом файле не попадают в заданный диапазон – в этом случае прерываем ввод и удаляем дерево.
Добавляемое значение не попадает в заданный диапазон – такие значения не должны добавляться.

4. Формат представления данных в файле

Дерево – структура нелинейная. Поэтому в файле надо отмечать, где кончается каждая ветвь дерева. Для этого будем использовать символ *, т.е. если у вершины нет левой и/или правой подвершины, ставим одну или две звёздочки (реализуем обход дерева в прямом порядке, сначала обрабатываем левое поддерево, затем правое). Поскольку звёздочка не является числом, нельзя просто вводить числовые данные – надо вводить строку, и, если она не равна '*', преобразовывать её в целое или вещественное число с помощью функций StrToInt и StrToFloat. Отдельные значения лучше записывать на разных строках. С символами проще, их можно все записать на одной строке вперемешку с символом *. Если в каких-то вариантах символ * попадает в диапазон допустимых значений, исключаем его из рассмотрения и как данные не используем.

Дерево	Содержимое файла
	1 2 3 4 * * 5 * * * 6 * 7 * *

5. Тестовые примеры

№ теста	Входные данные	Ожидаемые результаты	Смысл теста
1	3 1 4 0 5 2 6	k = 2	Есть элементы, удовлетворяющие условию.
2	3 1 4 -1 2	k = 0	Нет элементов, удовлетворяющих условию.

6. Метод

Для обработки дерева требуется рекурсия. Если вершина не имеет поддеревьев, то результат зависит от данных этой вершины. В противном случае результат равен сумме количества элементов, удовлетворяющих условию, в левом и правом поддеревьях плюс 1, если данные вершины удовлетворяют условию.