Лабораторная работа №10(дерево)
Тема: Двоичное бинарное дерево
Цель: получение навыков по созданию иерархических структур
ЗАДАНИЕ
- Разработать класс бинарное дерево, включив в него методы: конструктор по умолчанию и вывод бинарного дерева, используя прямой обход дерева.
- Разработать производный класс для дерева определенного вариантом. В класс включить методы:
· Конструктор с параметром (для сбалансированного дерева) – число узлов.
· Копирующий конструктор
· Деструктор
· Методы для операций, определенных в варианте.
- В нечетном варианте использовать бинарное дерево поиска, а в четном – сбалансированное бинарное дерево поиска (ЕСЛИ ВАРИАНТ НЕ ПРЕДУСМАТРИВАЕТ СВОЮ СТРУКТУРУ).
Варианты
1.Информационная часть узла содержит целое значение.
· Определить сумму значений находящихся в листьях дерева.
· Обойти дерево алгоритмом прямого обхода
· Удалить максимальный элемент дерева (считать, что такой элемент один)
· Вставить новый элемент
2.Информационная часть узла содержит символьное значение.
· Определить сумму цифр, содержащихся в дереве, применив алгоритм симметричного обхода
· Найти первое вхождение заданного символа и вернуть указатель на узел
· Найти максимальное значение среди листьев дерева
3. Информационная часть узла содержит целое значение.
· Определить среднее арифметическое всех узлов непустого дерева
· Найти сумму максимального и минимального элементов дерева
· Удалить самый левый лист дерева
4. Информационная часть узла содержит слово.
· Определить длину пути в дереве от корня до узла с заданным значением.
· Определить число листьев в дереве
· Определить высоту дерева
5. Информационная часть узла содержит символьное значение.
· Определить уровень, на котором находится узел с заданным значением.
· Вставить новый узел в дерево
· Удалить узел, содержащий заданное значение (первое вхождение)
6. Информационная часть узла целое число.
· Заменить в дереве все отрицательные значения на их модули
· Найти минимальное значение, хранящееся в дереве.
· Обойти дерево “в ширину”.
7. Информационная часть узла - символ.
· Выполнить алгоритм обратного обхода дерева.
· Определить, количество цифр в дереве.
· Удалить узлы, содержащие цифры.
8. Информационная часть узла содержит символ значение.
· Определить, содержится ли в дереве заданный символ.
· Вывести значения всех узлов поддерева с заданным значением узла.
· Определить высоту поддерева с заданным значением узла.
9. Информационная часть узла содержит текст и количество в нем цифр
· Определите количество узлов, текст которых содержит максимальное число цифр.
· Удалить узел, не содержащий в тексте цифр.
· Обойти дерево в обратном порядке и вывести значения его узлов.
10. Англо русский словарь построен как двоичное дерево поиска, упорядоченное по английскому слову. Каждый узел дерева содержит информацию: английское слово, русское слово, количество обращений.
· Включить узел в дерево
· Сформировать новое двоичное дерево поиска, упорядочивая узлы по числу обращений
· Вывести новый и старый словарь по иерархии сверху вниз.
11. На междугородней телефонной станции картотека абонентов, содержащая сведения: номер телефона и сведения о владельце, организована как бинарное упорядоченное дерево.
Определите операции:
· Формирование списка абонентов, упорядоченного по номеру телефона.
· Поиск сведений о владельце по введенному номеру
· Формирует извещение на оплату разговора по введенному номеру и времени за разговор
12. Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные охраняться в виде сбалансированного двоичного дерева.
Определите операции:
· Поиск информации по номеру введенного поезда
· Формирование списка поездов, отправляющихся с заданной станции
· Определить, количество поездов, которые следуют до заданной станции.
13. Формулу вида
<формула>::=цифра | (<формула> знак <формула>)
<знак>::= +|*|-
можно представить в виде бинарного дерева. Формула из одной цифры – это дерево из одной вершины. Формула вида F1 # F2 представлена деревом, у которого в корне – операция #, левое дерево это формула F1 , а правое – F2.
Определите операции:
· Построить дерево указанного вида
· Вычислить значение дерева
· Распечатать формулу дерева
14. Составить программу формирующую “перекрестные ссылки”, т.е. печатающую список слов, которые встречаются в анализируемом файле. А для каждого слова - список номеров строк, в которых это слово встречается. Информация по слову хранится в узле бинарного дерева поиска, упорядоченного по значению слова. Список номеров строк храниться в отдельном связанном списке, указатель на который хранит соответствующий узел дерева.
· Построить дерево указанного вида
· Найти слово, встретившееся в тексте в максимальном числе строк
· Вычислить значение дерева
· Распечатать формулу дерева