Программная реализация добавления данных в упорядоченное двоичное дерево
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
м, если для каждой вершины дерева все ключи в ее левом поддереве меньше ключа этой вершины, а все ключи в ее правом поддереве больше ключа вершины.
Деревья поиска являются одной из наиболее эффективных структур построения упорядоченных данных. Как известно, в упорядоченном массиве очень эффективно реализуется поиск (дихотомия), но очень тяжело выполнить добавление и удаление элементов. Наоборот, в упорядоченном списке легко реализуется добавление и удаление элементов, но не эффективна реализация поиска из-за необходимости последовательного просмотра всех элементов, начиная с первого. Деревья поиска позволяют объединить преимущества массивом и линейных списков: легко реализуется добавление и удаление элементов, а также эффективно выполняется поиск.
Дерево поиска следует использовать для представления упорядоченных данных, когда число их достаточно велико и часто приходится выполнять операции добавления, удаления и поиска, [4].
Проектный раздел
бинарный дерево двоичный программный
Словесная постановка задачи: программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.
Формальная постановка задачи:
Входные данные: элементы, которые будут добавляться в дерево (целые числа).
Выходные данные: дерево из добавленных элементов (целые числа).
Метод решения: добавление элемента в двоичное дерево будет происходить по следующему алгоритму: прежде всего, надо найти подходящее место для нового элемента, поэтому добавление неразрывно связано с процедурой поиска. Будем считать, что в дерево могут добавляться элементы с одинаковыми ключами, и для этого с каждой вершиной свяжем счетчик числа появления этого ключа.
В процессе поиска может возникнуть одна из двух ситуаций:
1)найдена вершина с заданным значением ключа, и в этом случае просто увеличивается счетчик;
2)поиск надо продолжать по пустой ссылке, что говорит об отсутствии в дереве искомой вершины, более того, тем самым определяется место в дереве для размещения новой вершины.
Само добавление включает следующие шаги:
1)выделение памяти для новой вершины;
2)формирование информационной составляющей;
)формирование двух пустых ссылочных полей на будущих потомков;
)формирование в родительской вершине левого и правого ссылочного поля - адреса новой вершины.
Здесь только последняя операция вызывает некоторую сложность, поскольку для доступа к ссылочному полю родительской вершины надо знать ее адрес.
Ситуация аналогична добавлению элемента в линейный список перед заданным, когда для отслеживания элемента-предшественника при проходе по списку использовался дополнительный указатель. Этот же прием можно использовать и для деревьев, но есть более элегантное решение - рекурсивный поиск с добавлением новой вершины при необходимости. Каждый рекурсивный вызов отвечает за обработку очередной вершины дерева, начиная с корня, а вся последовательность вложенных вызовов позволяет автоматически запоминать путь от корня до любой текущей вершины. Процедура поиска должна иметь формальный параметр-переменную ссылочного типа, который отслеживает адрес текущей вершины дерева и как только этот адрес становится пустым, создается новая вершина и ее адрес возвращается в вызвавшую процедуру, тем самым автоматически формируя необходимую ссылку в родительской вершине.
Алгоритм (блок-схемы):
Общая блок-схема действий, а также блок-схемы поиска места для элемента и создание вершины (добавления данных) в упорядоченное двоичное дерево представлены на рисунках 4, 5 и 6 соответственно.
Рисунок 4 - Общая блок-схема действий
Рисунок 5 - Блок-схема поиска места для элемента
Рисунок 6 - Блок-схема добавления элемента
Программный раздел
Программа реализована в среде Visual Studio 2008 в консольном приложении Win 32. Проект состоит из одного файла с расширением .cpp.
Сначала создается структура binary_tree, в которой объявляются следующие переменные: data - вводимые данные, count - счетчик (оба целые числа), указатели на правое и левое поддеревья binary_tree *left, *right:
struct binar_tree
{data, count;_tree *left, *right;
};
Также глобально обнуляется счетчик count = 0 и корню дерева root присваивается значение NULL. Для решения задачи добавления данных в упорядоченное двоичное дерево нужно создать функцию добавления элементов в это самое дерево Add(). Также понадобится функция просмотра дерева Show(), чтобы убедиться, что элементы добавляются правильно, и функция очистки дерева Clear() на случай, если возникнет необходимость очистить дерево. Каждая функция основана на рекурсии, то есть вызывает саму себя там, где это необходимо. Прототипы этих функций и описание каждой из них приведено ниже:
1)функция void Add(struct binar_tree **current, int data): чтобы начать добавлять элементы в дерево, нужно проверить текущий элемент. Если он не пустой (current != NULL), то проверяется следующее условие: если элемент меньше текущего, то он добавляется в левое поддерево, иначе если элемент больше текущего, то он добавляется в правое поддерево, иначе счетчик count увеличивается на единицу. Иначе если все же current == NULL, то создается функцией new новое дерево binary_tree. После данные записываются (*current)data = data, левому и правому поддеревьям присваиваются значения NULL, счетчику count становится равным 1 и этот же самый счетчик увеличивается на единицу.
2)функция void Show(struct binar_tree *current, int l): чтобы начать просмотр, нужно опять же пр?/p>