Программная реализация добавления данных в упорядоченное двоичное дерево
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Содержание
Аннотация
Введение
Теоретический раздел
.1 Определение бинарного дерева
.2 Упорядоченное двоичное дерево и его свойства
. Двоичные деревья поиска
Проектный раздел
Программный раздел
Экспериментальный раздел
Заключение
Список использованных источников
Приложение I
Введение
Организация данных с помощью бинарных деревьев облегчает программирование и позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени.
Основной целью данной работы является изучение фундаментальной абстрактной структуры - дерево, а также программная реализация добавления данных в упорядоченное двоичное дерево. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C/C++.
Для достижения цели были поставлены и решены следующие задачи:
) закрепить практические навыки программирования на языке Си;
)сформулировать задачу;
)исходя из поставленной цели, построить правильный и наиболее оптимальный алгоритм;
)реализовать его на изучаемом языке программирования;
)описать результаты.
Первый раздел посвящен определению бинарного дерева, упорядоченного двоичного дерева, бинарного дерева поиска, а также описанию основных свойств и особенностей структур таких деревьев. Второй раздел посвящен описанию формальной постановки задачи, метода решения добавления данных в дерево и исследованию и выбора алгоритма. Третий раздел содержит сведения о логической структуре и функционировании программы, описание используемых функций. Четвертый раздел включает тестирование программы, оценку полноты решения поставленной задачи и достоверности полученных результатов.
Теоретический раздел
1.1 Определение бинарного дерева
Бинарное (двоичное) дерево - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значения данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значения данного узла.
Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом.
Схематичное изображение бинарного дерева представлено на рисунке 1:
Рисунок 1 - Схематичное изображение бинарного дерева
Бинарное дерево может выродиться в список, представленный на рисунке 2:
Рисунок 2 - Схематичное изображение списка
Особенность структуры таких деревьев проявляется в том, что она явно реализует методы бинарного поиска, т.к. каждый узел дерева имеет 2 указателя, т.е. 2 альтернативы пути поиска. Если искомый ключ больше, чем ключ вершины, то дальнейший поиск осуществляется по правому поддереву, в противном случае по левому. В отличие от бинарного поиска в последовательном списке, в бинарном дереве не требуется никаких вычислений дальнейшего пути поиска.
Строго двоичным деревом называется дерево, у которого каждая внутренняя вершина имеет непустые левое и правое поддеревья. Это означает, что в строго двоичном дереве нет вершин, у которых есть только одно поддерево.
Полным двоичным деревом называется дерево, у которого все листья находятся на одном уровне и каждая внутренняя вершина имеет непустые левое и правое поддеревья, [1].
1.2 Упорядоченное двоичное дерево и его свойства
Упорядоченным называется такое дерево, в котором упорядочены все потомки каждой вершины. Принято считать, что на диаграмме деревья изображаются так, чтобы все потомки были упорядочены слева направо. Двоичное (бинарное) дерево можно определить как упорядоченное дерево, каждая вершина которого имеет не более двух потомков, причем каждый из потомков считается либо левым, либо правым потомком своего родителя. Поддерево, корень которого находится в левом (правом) потомке вершины, называется левым (правым) поддеревом этой вершины.
Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства:
) все элементы в левом поддереве меньше элемента, хранимого в x;
) все элементы в правом поддереве больше элемента, хранимого в x;
) все элементы дерева различны, [3].
Пример упорядоченного двоичного дерева представлен на рисунке 3:
Рисунок 3 - Упорядоченное двоичное дерево
Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. Основными операциями, производимыми с упорядоченным деревом, являются:
) поиск вершины;
) добавление вершины;
) удаление вершины;
) вывод (печать) дерева;
) очистка дерева, [2].
2. Двоичные деревья поиска
Деревья поиска - частный, но практически, пожалуй, наиболее важный вид двоичных деревьев. Будем считать, что каждая вершина имеет некое ключевое поле, позволяющее упорядочить множество вершин. Двоичное дерево называется деревом поиска или поисковым дерево