Лабораторная работа №10(дерево)

Тема: Двоичное бинарное дерево

Цель: получение навыков по созданию иерархических структур

 

ЗАДАНИЕ

  1. Разработать класс бинарное дерево, включив в него методы: конструктор по умолчанию и вывод бинарного дерева, используя прямой обход дерева.
  2. Разработать производный класс для дерева определенного вариантом. В класс включить методы:

· Конструктор с параметром (для сбалансированного дерева) – число узлов.

· Копирующий конструктор

· Деструктор

· Методы для операций, определенных в варианте.

  1. В нечетном варианте использовать бинарное дерево поиска, а в четном – сбалансированное бинарное дерево поиска (ЕСЛИ ВАРИАНТ НЕ ПРЕДУСМАТРИВАЕТ СВОЮ СТРУКТУРУ).

 

Варианты

1.Информационная часть узла содержит целое значение.

· Определить сумму значений находящихся в листьях дерева.

· Обойти дерево алгоритмом прямого обхода

· Удалить максимальный элемент дерева (считать, что такой элемент один)

· Вставить новый элемент

 

2.Информационная часть узла содержит символьное значение.

· Определить сумму цифр, содержащихся в дереве, применив алгоритм симметричного обхода

· Найти первое вхождение заданного символа и вернуть указатель на узел

· Найти максимальное значение среди листьев дерева

 

3. Информационная часть узла содержит целое значение.

· Определить среднее арифметическое всех узлов непустого дерева

· Найти сумму максимального и минимального элементов дерева

· Удалить самый левый лист дерева

 

4. Информационная часть узла содержит слово.

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

· Определить число листьев в дереве

· Определить высоту дерева

 

5. Информационная часть узла содержит символьное значение.

· Определить уровень, на котором находится узел с заданным значением.

· Вставить новый узел в дерево

· Удалить узел, содержащий заданное значение (первое вхождение)

 

6. Информационная часть узла целое число.

· Заменить в дереве все отрицательные значения на их модули

· Найти минимальное значение, хранящееся в дереве.

· Обойти дерево “в ширину”.

 

7. Информационная часть узла - символ.

· Выполнить алгоритм обратного обхода дерева.

· Определить, количество цифр в дереве.

· Удалить узлы, содержащие цифры.

 

8. Информационная часть узла содержит символ значение.

· Определить, содержится ли в дереве заданный символ.

· Вывести значения всех узлов поддерева с заданным значением узла.

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

 

9. Информационная часть узла содержит текст и количество в нем цифр

· Определите количество узлов, текст которых содержит максимальное число цифр.

· Удалить узел, не содержащий в тексте цифр.

· Обойти дерево в обратном порядке и вывести значения его узлов.

 

10. Англо русский словарь построен как двоичное дерево поиска, упорядоченное по английскому слову. Каждый узел дерева содержит информацию: английское слово, русское слово, количество обращений.

· Включить узел в дерево

· Сформировать новое двоичное дерево поиска, упорядочивая узлы по числу обращений

· Вывести новый и старый словарь по иерархии сверху вниз.

 

11. На междугородней телефонной станции картотека абонентов, содержащая сведения: номер телефона и сведения о владельце, организована как бинарное упорядоченное дерево.

Определите операции:

· Формирование списка абонентов, упорядоченного по номеру телефона.

· Поиск сведений о владельце по введенному номеру

· Формирует извещение на оплату разговора по введенному номеру и времени за разговор

 

12. Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные охраняться в виде сбалансированного двоичного дерева.

Определите операции:

· Поиск информации по номеру введенного поезда

· Формирование списка поездов, отправляющихся с заданной станции

· Определить, количество поездов, которые следуют до заданной станции.

 

13. Формулу вида

<формула>::=цифра | (<формула> знак <формула>)

<знак>::= +|*|-

можно представить в виде бинарного дерева. Формула из одной цифры – это дерево из одной вершины. Формула вида F1 # F2 представлена деревом, у которого в корне – операция #, левое дерево это формула F1 , а правое – F2.

Определите операции:

· Построить дерево указанного вида

· Вычислить значение дерева

· Распечатать формулу дерева

 

14. Составить программу формирующую “перекрестные ссылки”, т.е. печатающую список слов, которые встречаются в анализируемом файле. А для каждого слова - список номеров строк, в которых это слово встречается. Информация по слову хранится в узле бинарного дерева поиска, упорядоченного по значению слова. Список номеров строк храниться в отдельном связанном списке, указатель на который хранит соответствующий узел дерева.

· Построить дерево указанного вида

· Найти слово, встретившееся в тексте в максимальном числе строк

· Вычислить значение дерева

· Распечатать формулу дерева