Тема 3 двоичные деревья Разработать и реализовать программу создания и обработки двоичного дерева. Узел (вершина) дерева содержит одно информационное поле целого типа.
При реализации на языке Паскаль программа должна иметь модульную структуру [ 5 ].
Программа должна содержать меню с перечнем возможностей работы с двоичным деревом и оператор выбора соответствующего пункта меню с обращением к подпрограмме ( процедуре или функции ), реализующей выбранное действие над деревом.
Модуль ( unit ) должен содержать описание соответствующих типов и подпрограмм работы с деревом:
а) создание дерева:
– создание дерева поиска, используя рекурсивную процедуру добавления (включения) узла в дерево ( данные читаются из текстового файла или вводятся с клавиатуры);
б) обход дерева:
– рекурсивная процедура обхода дерева сверху вниз (префиксного обхода);
– рекурсивная процедура обхода дерева снизу вверх (постфиксного обхода);
– рекурсивная процедура обхода дерева слева направо (инфиксного обхода);
– рекурсивная процедура обхода дерева справа налево (см. [1], [2], [8] ) и вывода значения узла дерева на экран с выделением каждого уровня с помощью соответствующего отступа (корень дерева находится на нулевом уровне).
в) рекурсивная обработка узлов дерева ( Задание 1 );
Задание 1
Описать рекурсивную подпрограмму (процедуру или функцию) решения задачи.
Определить количество узлов дерева с заданным значением.
Определить количество узлов дерева с нулевыми значениями.
Определить количество узлов дерева с положительными значениями.
Определить количество узлов дерева с отрицательными значениями.
Определить количество узлов дерева с четными значениями.
Определить количество узлов дерева с нечетными значениями.
Найти сумму значений всех листьев дерева.
Найти сумму значений внутренних узлов дерева.
Найти сумму положительных значений в узлах дерева.
Найти сумму отрицательных значений в узлах дерева.
Найти сумму четных значений в узлах дерева.
Найти сумму нечетных значений в узлах дерева.
Найти произведение значений всех листьев дерева.
Найти произведение положительных значений в узлах дерева.
Найти произведение отрицательных значений в узлах дерева.
Найти произведение четных значений в узлах дерева.
Найти произведение нечетных значений в узлах дерева.
Вычислить среднее арифметическое значений всех узлов дерева.
Вычислить среднее арифметическое положительных значений в узлах дерева.
Вычислить среднее арифметическое отрицательных значений в узлах дерева.
Определить количество внутренних узлов дерева.
Определить количество узлов дерева, имеющих только левого потомка.
Определить количество узлов дерева, имеющих только правого потомка.
Определить количество узлов дерева, не имеющих левого потомка.
Определить количество узлов дерева, не имеющих правого потомка.
Литература
1 Вирт Н. Алгоритмы + структуры данных = программы. – М.: 1985. – 406 с.
2 Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.–360 с.
3 Задачи по программированию / Абрамов С.А. и др. – М.: Наука, 1988. –224 с.
4 Задачи по программированию / Амелина Н.И. и др. – М.: Вузовская книга, 2000. – 104 с.
5 Методы программирования. Учебное пособие / Н.И. Минакова, Е.С. Невская, Г.А. Угольницкий, А.А. Чекулаева, М.И. Чердынцева. – М.: Вузовская книга, 1999. – 280 с.
6 Пильщиков В.Н. Сборник упражнений по языку Паскаль. – М.: Наука, 1989. – 160 с.
7 Амелина Н.И. Линейные односвязные списки. Методические указания по курсу «Языки программирования и методы трансляции» для студентов 1 и 2 курсов дневного и вечернего отделений факультета математики, механики и компьютерных наук – Ростов–на–Дону, ЮФУ, 2009. – 36 с.
8 Амелина Н.И., Чердынцева М.И. Структуры данных. Деревья. Методические указания по курсу «Языки программирования и методы трансляции» для студентов 1 и 2 курсов дневного и вечернего отделений факультета математики, механики и компьютерных наук. – Ростов–на–Дону: УПЛ ЮФУ, 2007. – 34 с.
9 Чекулаева А.А., Спивак И.Г. Динамические структуры данных. Методические указания для студентов вечернего отделения механико-математического факультета. – Ростов-на-Дону, УПЛ РГУ, 1998. – 36 с.