Определение бинарного дерева

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ»

ЭЛЕКТРОТЕХНИЧЕСКИЙ ФАКУЛЬТЕТ

Кафедра систем информатики

Курсовой проект

по дисциплине «Программирование на языке высокого уровня С/С++»

Тема: «Добавление данных в упорядоченное двоичное дерево»

Выполнила: студентка гр. Б-662

___________ Бардаханова Н.Е.

Руководитель: доцент каф. СИ

___________ Хаптахаева Н.Б.

Оценка: ______________

Дата защиты: ______________

Улан-Удэ

Аннотация

Введение

Двоичные (бинарные) деревья часто используются для хранения информации. Они выгодно отличаются от массивов фиксированного размера своим динамическим характером, возможностью почти неограниченно увеличивать объемы хранимой информации. От линейных списков их отличают лучшие временные характеристики - например, при поиске элемента (наиболее часто используемой операции) требуется в среднем просмотреть меньшую часть дерева, чем это требовалось бы для списка с таким же количеством элементов.

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

Основной целью курсового проекта является развитие и закрепление знаний и навыков по двум дисциплинам «Программирование» и «Структуры и алгоритмы обработки данных».

Для достижения цели проекта были поставлены и решены следующие задачи:

1) детальное изучение предметной области поставленной задачи, расширенная постановка задачи;

2) изучение дополнительных средств языка С и С++, предназначенных для работы с графикой;

3) разработка алгоритмов;

4) программная реализация разработанных алгоритмов;

5) тестирование разработанного программного обеспечения.

Расчетно-пояснительная записка состоит из введения, ? разделов, заключения, ? приложений.

В первом разделе приведено …

Здесь нужно описать содержание всех разделов и приложений. Это можно сделать после того как будет готово РПЗ.

Теоретический раздел

Определение бинарного дерева

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

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

Схематичное изображение бинарного дерева представлено на рисунке 1:

Рисунок 1 – Схематичное изображение бинарного дерева

Бинарное дерево может выродиться в список, представленный на рисунке 2:

Рисунок 2 – Схематичное изображение списка