Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.
Аннотация к работе
Организация данных с помощью бинарных деревьев облегчает программирование и позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C/C .Бинарное (двоичное) дерево - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значения данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значения данного узла. Схематичное изображение бинарного дерева представлено на рисунке 1: Рисунок 1 - Схематичное изображение бинарного дерева Бинарное дерево может выродиться в список, представленный на рисунке 2: Рисунок 2 - Схематичное изображение списка Особенность структуры таких деревьев проявляется в том, что она явно реализует методы бинарного поиска, т.к. каждый узел дерева имеет 2 указателя, т.е.Упорядоченным называется такое дерево, в котором упорядочены все потомки каждой вершины. Принято считать, что на диаграмме деревья изображаются так, чтобы все потомки были упорядочены слева направо. Двоичное (бинарное) дерево можно определить как упорядоченное дерево, каждая вершина которого имеет не более двух потомков, причем каждый из потомков считается либо левым, либо правым потомком своего родителя. Поддерево, корень которого находится в левом (правом) потомке вершины, называется левым (правым) поддеревом этой вершины.Деревья поиска - частный, но практически, пожалуй, наиболее важный вид двоичных деревьев. Двоичное дерево называется деревом поиска или поисковым деревом, если для каждой вершины дерева все ключи в ее левом поддереве меньше ключа этой вершины, а все ключи в ее правом поддереве больше ключа вершины.Формальная постановка задачи: Входные данные: элементы, которые будут добавляться в дерево (целые числа). Метод решения: добавление элемента в двоичное дерево будет происходить по следующему алгоритму: прежде всего, надо найти подходящее место для нового элемента, поэтому добавление неразрывно связано с процедурой поиска. Будем считать, что в дерево могут добавляться элементы с одинаковыми ключами, и для этого с каждой вершиной свяжем счетчик числа появления этого ключа. В процессе поиска может возникнуть одна из двух ситуаций: 1) найдена вершина с заданным значением ключа, и в этом случае просто увеличивается счетчик; 2) поиск надо продолжать по пустой ссылке, что говорит об отсутствии в дереве искомой вершины, более того, тем самым определяется место в дереве для размещения новой вершины.Сначала создается структура binary_tree, в которой объявляются следующие переменные: data - вводимые данные, count - счетчик (оба целые числа), указатели на правое и левое поддеревья binary_tree *left, *right: struct binar_tree Также понадобится функция просмотра дерева Show(), чтобы убедиться, что элементы добавляются правильно, и функция очистки дерева Clear() на случай, если возникнет необходимость очистить дерево. Прототипы этих функций и описание каждой из них приведено ниже: 1) функция void Add(struct binar_tree **current, int data): чтобы начать добавлять элементы в дерево, нужно проверить текущий элемент. Если он не пустой (current != NULL), то проверяется следующее условие: если элемент меньше текущего, то он добавляется в левое поддерево, иначе если элемент больше текущего, то он добавляется в правое поддерево, иначе счетчик count увеличивается на единицу. 3) функция void Clear(struct binar_tree **current): как и в предыдущих двух функциях, очистка дерева начинается с той самой проверки текущего элемента: если он не равен NULL, то очищаются левые и правые поддеревья, удаляется текущий элемент, счетчик count уменьшается на единицу, и, если этот самый счетчик равен нулю, то текущему значению присваивается NULL.Для того чтобы проверить, работает ли программа правильно, выполнены ли все условия задачи, необходимо провести тестирование. Процесс тестирование разделен на 3 этапа: 1) Проверка в нормальных условиях (программа должна показать правильные результаты для характерных совокупностей данных): Сначала выбранным действием №2 осуществляется просмотр дерева, чтобы убедиться, пустое оно или нет. Затем действием №1 добавляется первый элемент 70. Результат работы программы представлен на рисунке 5. Проверка в экстремальных условиях (проверка работоспособности программы для граничных значений области изменения входных переменных, реакция программы на «нулевые примеры» и т.д.): Если при выборе действия №1 - добавление элемента вводить с клавиатуры вещественные числа или символы, то произойдет сбой работы программы, т.к. тип вводимых данных исключительно целые числа.В процессе вып
План
Содержание
Аннотация
Введение
Теоретический раздел
1.1 Определение бинарного дерева
1.2 Упорядоченное двоичное дерево и его свойства
2. Двоичные деревья поиска
Проектный раздел
Программный раздел
Экспериментальный раздел
Заключение
Список использованных источников
Приложение I
Введение
Организация данных с помощью бинарных деревьев облегчает программирование и позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени.
Основной целью данной работы является изучение фундаментальной абстрактной структуры - дерево, а также программная реализация добавления данных в упорядоченное двоичное дерево. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C/C .
Для достижения цели были поставлены и решены следующие задачи: 1) закрепить практические навыки программирования на языке Си;
1) сформулировать задачу;
2) исходя из поставленной цели, построить правильный и наиболее оптимальный алгоритм;
3) реализовать его на изучаемом языке программирования;
4) описать результаты.
Первый раздел посвящен определению бинарного дерева, упорядоченного двоичного дерева, бинарного дерева поиска, а также описанию основных свойств и особенностей структур таких деревьев. Второй раздел посвящен описанию формальной постановки задачи, метода решения добавления данных в дерево и исследованию и выбора алгоритма. Третий раздел содержит сведения о логической структуре и функционировании программы, описание используемых функций. Четвертый раздел включает тестирование программы, оценку полноты решения поставленной задачи и достоверности полученных результатов.