Файл: Лабораторная работа 1 5 Бинарные деревья 5 Цель работы 5 Краткие теоретические сведения 5 Постановка задачи 6.docx

Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования

Пермский национальный исследовательский

политехнический университет

Кафедра «Информационные технологии и автоматизированные системы»

Структурное и объектно-ориентированное программирование на С++.

Лабораторный практикум.

Часть III.

Представление графических объектов и проектирование программ на С++.


Авторы: Бартов Е.И.,
Ерохин Н.В., Торопицын М.С.

Пермь, 2018

Оглавление

---

Лабораторная работа № 1

---

Бинарные деревья

1. 
   
   

   1. Цель работы:

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

2. Краткие теоретические сведения

Бинарное дерево – это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка.

Описать такую структуру можно следующим образом:

struct point

{

int data;//информационное поле

point *left;//адрес левого поддерева

point *right;//адрес правого поддерева

};

Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.

Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева — больше, оно называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму количества узлов.

В идеально сбалансированном дереве количество узлов справа и слева отличается не более чем на единицу.

Линейный список можно представить как вырожденное бинарное дерево, в котором каждый узел имеет не более одной ссылки. Для списка среднее время поиска равно половине длины списка.

Деревья и списки являются рекурсивными структурами, т. к. каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:

• 
  либо пустой структурой;
  
• 
  либо элементом, с которым связано конечное число поддеревьев.
  

Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.

---

Обход дерева

Для того, чтобы выполнить определенную операцию над всеми узлами дерева, все узлы надо обойти. Такая задача называется обходом дерева. При обходе узлы должны посещаться в определенном порядке. Существуют три принципа упорядочивания. Рассмотрим дерево, представленное на рисунке 1.1:


Рисунок 1.1 – Бинарное дерево
На этом дереве можно определить три метода упорядочивания:

Слева направо: Левое поддерево – Корень – Правое поддерево;

Сверху вниз: Корень – Левое поддерево – Правое поддерево;

Снизу вверх: Левое поддерево – Правое поддерево – Корень.

Эти три метода можно сформулировать в виде рекурсивных алгоритмов.

void Run(point*p)

//обход слева направо

{

if(p)

{

<обработка p->data>

Run(p->left);//переход к левому поддереву

Run(p->right);//переход к правому поддереву

}

}

Если в качестве операции обработки узла поставить операцию вывода информационного поля, то мы получим функцию для печати дерева.

3. Постановка задачи

1. Сформировать идеально сбалансированное бинарное дерево, тип информационного поля указан в варианте.

2. Распечатать полученное дерево.

3. Выполнить обработку дерева в соответствии с заданием, вывести полученный результат.

4. Преобразовать идеально сбалансированное дерево в дерево поиска.

5. Распечатать полученное дерево.

4. Варианты заданий

1 . Тип информационного поля char. Найти количество элементов с заданным ключом.

2. Тип информационного поля int. Найти максимальный элемент в дереве.

3 . Тип информационного поля char*. Найти количество листьев в дереве.

4 . Тип информационного поля double. Найти минимальный элемент в дереве.

5 . Тип информационного поля char. Найти высоту дерева.

6 . Тип информационного поля int. Найти среднее арифметическое элементов дерева.

7 . Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа.

8. Тип информационного поля char. Найти количество элементов с заданным ключом.

9 . Тип информационного поля double. Найти максимальный элемент в дереве.

---

10. Тип информационного поля int. Найти количество листьев в дереве.

11. Тип информационного поля double. Найти минимальный элемент в дереве.

12. Тип информационного поля char. Найти высоту дерева.

13. Тип информационного поля int. Найти среднее арифметическое элементов дерева.

14. Тип информационного поля char. Найти количество элементов с заданным ключом.

15. Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа

16. Тип информационного поля int. Найти максимальный элемент в дереве.

17. Тип информационного поля double. Найти количество листьев в дереве.

18. Тип информационного поля int. Найти минимальный элемент в дереве.

19. Тип информационного поля char. Найти высоту дерева.

20. Тип информационного поля double. Найти среднее арифметическое элементов дерева.

21. Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа.

22. Тип информационного поля char. Найти количество элементов с заданным ключом.

23. Тип информационного поля char*. Найти количество листьев в дереве.

24. Тип информационного поля double. Найти максимальный элемент в дереве.

25. Тип информационного поля double. Найти минимальный элемент в дереве.

5. Методические указания

1. Описания структур для формирования деревьев, а также функции для их обработки сохранить в библиотечном файле с расширением .h (например, point.h). Функцию main() сохранить в файле с расширением .cpp. Библиотечный файл подключить с помощью директивы #include “имя_файла.h”.

2. Для выделения памяти под информационные поля типа char* использовать операцию new, для удаления из памяти – операцию delete.

3. Для формирования элементов дерева написать отдельные функции.

4. Для формирования дерева, удаления добавления элементов, поиска заданных элементов написать отдельные функции.

5. В функции main() должны быть размещены только описания переменных и обращения к соответствующим функциям.

6. Если в дереве отсутствуют элементы, соответствующие критерию поиска (например, при удалении элемента с номером k, k больше, чем количество элементов в списке), должно быть выведено сообщение о том, что требуемые элементы не найдены.

---