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

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

Федеральное государственное бюджетное образовательное

учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

БИНАРНЫЕ ДЕРЕВЬЯ

Отчёт по лабораторной работе №1 по дисциплине

«Структуры и алгоритмы обработки данных на ЭВМ»

                                                                          Студент гр. з-431П10-5

Иван Михайлович Пивоваров

                                                                             Направления подготовки

                                                 09.03.01

                                                         Вариант №2

                                                                      «14» февраля 2021 г.

                                                                                  Проверил:

                                                                              Старший преподаватель                                                        

                                                          каф.  КСУП                                                                              

                                                              Е.И. Потапова

                                                                               «__»___________2021 г.

2021

ЛАБОРАТОРНАЯ РАБОТА № 1

«БИНАРНЫЕ ДЕРЕВЬЯ»

Цель лабораторной работы – получить практические навыки представления в памяти ЭВМ структуры данных «бинарное дерево», реализовать на языке программирования C/C++ алгоритмы работы с деревьями.

Индивидуальное задание:

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

Алгоритм решения задачи

Каждая вершина дерева описывается как структура, содержащая три поля: ключ и два ссылочных поля для адресации потомков:

Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную, пустое дерево определяется установкой переменной root в NULL.

Добавление в дерево – сначала задается корень (left, right принимают значение NULL), затем следующее добавляемое значение сравнивается с ключом корня и присваивается либо левой ветви дерева, либо правой. Дальнейшие значения добавляются к соответствующему узлу дерева.

Добавление ключа в дерево:

        если дерево пустое

выделяем память под узел

задаем информационную часть узла

задаем пустые ссылки на потомков

выходим из добавления ключа

иначе

        если новый ключ<ключа текущей вершины

                вызываем процедуру добавления для левого потомка

иначе

                вызываем процедуру добавления для правого потомка

Бинарное дерево можно определить как конечное множество узлов, которое может быть либо пустым, либо состоит из корня и двух непересекающихся бинарных деревьев (левого и правого поддеревьев), причем, каждое поддерево, в свою очередь, имеет такую же структуру. Поэтому для обхода дерева подходит рекурсивная реализация, в которой в качестве формального параметра берется корень дерева. Корень дерева при обходе слева направо проходится после того, как будут пройдена вся левая ветвь дерева до конца, затем будет пройдена правая ветвь.

Алгоритм обхода слева направо:

рекурсивно обработать левое поддерево текущего поддерева

вывести значение вершины текущего поддерева

рекурсивно обработать правое поддерево

Результаты работы программы

[pic 1]

Выводы

В процессе выполнения лабораторной работы были реализованы рекурсивные процедуры добавления ключа в бинарное дерево, обхода бинарного дерева слева направо, очистки дерева после завершения работы программы.

Приложение А. Листинг программы

#include <stdio.h>

#include <conio.h>