ЗАДАНИЕ 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