ЗАДАНИЕ 9. Деревья и польская запись

Вариант 1. Создание и обработка структур типа «дерево»

Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности:

– создание дерева;

– добавление новой записи;

– поиск информации по заданному ключу;

– удаление информации с заданным ключом;

– вывод информации;

– решение индивидуального задания;

– освобождение памяти при выходе из программы.

1. Поменять местами информацию, содержащую максимальный и минимальный ключи.

2. Подсчитать число листьев в дереве.

3. Удалить из дерева ветвь с вершиной, имеющей заданный ключ.

4. Определить глубину дерева.

5. Определить число узлов на каждом уровне дерева.

6. Удалить из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы.

7. Определить количество узлов с четными ключами.

8. Определить число листьев на каждом уровне дерева.

9. Определить число узлов в дереве, имеющих только одного потомка.

10. Определить количество узлов правой ветви дерева.

11. Определить количество записей в дереве, начинающихся с введенной с клавиатуры буквы.

12. Найти среднее значение всех ключей дерева и найти строку, имеющую ближайший к этому значению ключ.

13. Определить количество узлов левой ветви дерева.

14. Определить число узлов в дереве, имеющих двух потомков.

15. Найти запись с ключом, ближайшим к среднему значению между максимальным и минимальным значениями ключей.

Вариант 2. Создание и использование польской записи

Написать программу формирования обратной польской записи и расчета полученного выражения. Предусмотреть возможности того, что идентификаторы могут состоять более чем из одного символа и могут быть использованы операции % и возведение в степень. Результат работы программы проверить на конкретном примере (табл. 15.1).

Например, если ввести выражение (a + b)*(c – d)/e и значения переменных а = 3, b = 5, c = 6, d = 9, е = 7, должны получиться следующие результаты:

Постфиксная форма ab+cd– *e/

Результат расчета – 3.42857

Таблица 15.1

№	Выражение	a	b	c	d	e	Результат
	a/(b– c)*(d+e)	8.6	2.4	5.1	0.3	7.9	– 26.12
	(a+b)*(c– d)/e	7.4	3.6	2.8	9.5	0.9	– 81.89
	a– (b+c*d)/e	3.1	5.4	0.2	9.6	7.8	2.16
	a/b– ((c+d)*e)	1.2	0.7	9.3	6.5	8.4	– 131.006
	a*(b– c+d)/e	9.7	8.2	3.6	4.1	0.5	168.78
	(a+b)*(c– d)/e	0.8	4.1	7.9	6.2	3.5	2.38
	a*(b– c)/(d+e)	1.6	4.9	5.7	0.8	2.3	– 0.413
	a/(b*(c+d))– e	8.5	0.3	2.4	7.9	1.6	1.151
	(a+(b/c– d))*e	5.6	7.4	8.9	3.1	0.2	0.666
	a*(b+c)/(d– e)	0.4	2.3	6.7	5.8	9.1	– 1.091
	a– (b/c*(d+e))	5.6	3.2	0.9	1.7	4.8	– 17.51
	(a– b)/(c+d)*e	0.3	6.7	8.4	9.5	1.2	– 0.429
	a/(b+c– d*e)	7.6	4.8	3.5	9.1	0.2	1.173
	a*(b– c)/(d+e)	0.5	6.1	8.9	2.4	7.3	– 0.144
	(a+b*c)/(d– e)	9.1	0.6	2.4	3.7	8.5	– 2.196