Программная реализация добавления данных в упорядоченное двоичное дерево

• Содержание
• Аннотация
• Введение
• Теоретический раздел
• 1.1 Определение бинарного дерева
• 1.2 Упорядоченное двоичное дерево и его свойства
• 2. Двоичные деревья поиска
• Проектный раздел
• Программный раздел
• Экспериментальный раздел
• Заключение
• Список использованных источников
• Приложение I

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

Основной целью данной работы является изучение фундаментальной абстрактной структуры — дерево, а также программная реализация добавления данных в упорядоченное двоичное дерево. Кроме того, необходимо закрепить теоретические знания и практические навыки в программировании на языке высокого уровня C/C++.

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

1) закрепить практические навыки программирования на языке Си;

1) сформулировать задачу;

2) исходя из поставленной цели, построить правильный и наиболее оптимальный алгоритм;

3) реализовать его на изучаемом языке программирования;

4) описать результаты.

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

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

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

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

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

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

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

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

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

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

Строго двоичным деревом называется дерево, у которого каждая внутренняя вершина имеет непустые левое и правое поддеревья. Это означает, что в строго двоичном дереве нет вершин, у которых есть только одно поддерево.

Полным двоичным деревом называется дерево, у которого все листья находятся на одном уровне и каждая внутренняя вершина имеет непустые левое и правое поддеревья,.

1.2 Упорядоченное двоичное дерево и его свойства

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

Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства:

1) все элементы в левом поддереве меньше элемента, хранимого в x;

2) все элементы в правом поддереве больше элемента, хранимого в x;

3) все элементы дерева различны,.

Пример упорядоченного двоичного дерева представлен на рисунке 3:

Рисунок 3 — Упорядоченное двоичное дерево

Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным. Основными операциями, производимыми с упорядоченным деревом, являются:

1) поиск вершины;

2) добавление вершины;

3) удаление вершины;

4) вывод (печать) дерева;

5) очистка дерева,.

2. Двоичные деревья поиска

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

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

Дерево поиска следует использовать для представления упорядоченных данных, когда число их достаточно велико и часто приходится выполнять операции добавления, удаления и поиска,.

Проектный раздел

бинарный дерево двоичный программный

Словесная постановка задачи: программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.

Формальная постановка задачи:

Входные данные: элементы, которые будут добавляться в дерево (целые числа).

Выходные данные: дерево из добавленных элементов (целые числа).

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

В процессе поиска может возникнуть одна из двух ситуаций:

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

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

Само добавление включает следующие шаги:

1) выделение памяти для новой вершины;

2) формирование информационной составляющей;

3) формирование двух пустых ссылочных полей на будущих потомков;

4) формирование в родительской вершине левого и правого ссылочного поля — адреса новой вершины.

Здесь только последняя операция вызывает некоторую сложность, поскольку для доступа к ссылочному полю родительской вершины надо знать ее адрес.

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

Алгоритм (блок-схемы):

Общая блок-схема действий, а также блок-схемы поиска места для элемента и создание вершины (добавления данных) в упорядоченное двоичное дерево представлены на рисунках 4, 5 и 6 соответственно.

Рисунок 4 — Общая блок-схема действий

Рисунок 5 — Блок-схема поиска места для элемента

Рисунок 6 — Блок-схема добавления элемента

Программный раздел

Программа реализована в среде Visual Studio 2008 в консольном приложении Win 32. Проект состоит из одного файла с расширением .cpp.

Сначала создается структура binary_tree, в которой объявляются следующие переменные: data — вводимые данные, count — счетчик (оба целые числа), указатели на правое и левое поддеревья binary_tree *left, *right:

struct binar_tree

{

int data, count;

binar_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): чтобы начать просмотр, нужно опять же проверить текущий элемент: если он не пустой, то просматривается правое поддерево. Далее начинается цикл, в котором с помощью отступа «» и выводом данных currentdata, элементы будут отображаться на консоли в удобном для просмотра виде. После этого идет просмотр левого поддерева и т. д.

3) функция void Clear (struct binar_tree **current): как и в предыдущих двух функциях, очистка дерева начинается с той самой проверки текущего элемента: если он не равен NULL, то очищаются левые и правые поддеревья, удаляется текущий элемент, счетчик count уменьшается на единицу, и, если этот самый счетчик равен нулю, то текущему значению присваивается NULL.

В главной функции программы реализовано меню, в котором пользователь может выбрать любое действие, которое ему необходимо:

1) добавление элемента

2) просмотр дерева

3) очистка дерева

4) выход (с помощью функции exit (1)).

Все эти действия реализованы с помощью оператора switch (s), где s — номер выбранного действия (целое число). Если выбранное действие не соответствует ни одному из предложенных, то выводится сообщение об ошибке выбора действия.

Исходный код данной программы представлен в Приложении I.

Экспериментальный раздел

Для того чтобы проверить, работает ли программа правильно, выполнены ли все условия задачи, необходимо провести тестирование. Процесс тестирование разделен на 3 этапа:

1) Проверка в нормальных условиях (программа должна показать правильные результаты для характерных совокупностей данных):

Сначала выбранным действием № 2 осуществляется просмотр дерева, чтобы убедиться, пустое оно или нет. Затем действием № 1 добавляется первый элемент 70. Он записывается в вершину дерева, затем второй элемент 50, который будет находиться слева от вершины, т.к. 50 меньше, чем 70, и третий элемент 90, который запишется справа от вершины, т.к. он больше 70. И в конце действием № 2 просматривается полученное дерево. Результат работы программы представлен на рисунке 5.

Рисунок 5 — Результат работы программы при нормальных условия

2) Проверка в экстремальных условиях (проверка работоспособности программы для граничных значений области изменения входных переменных, реакция программы на «нулевые примеры» и т. д.):

Если при выборе действия № 1 — добавление элемента вводить с клавиатуры вещественные числа или символы, то произойдет сбой работы программы, т.к. тип вводимых данных исключительно целые числа. Если добавить число 0 в корень дерева, то добавленные отрицательные и положительные числа будут добавляться по правилам добавления, которые были описаны выше и никаких сбоев программы не произойдет. Результат работы программы при добавлении нуля и отрицательных чисел представлен на рисунке 6.

Рисунок 6 — Результат работы программы при экстремальных условиях

3) Проверка в исключительных ситуациях (проверяется, что произойдет, если программе придется иметь дело с данными, выходящими за рамки обработки ограниченного набора данных):

Если при выборе действия № 1 — добавления элемента вводить с клавиатуры очень большое число, например 10 000 000 000, то в дерево добавляются большие отрицательные числа и работа программы не корректна. Результат работы программы представлен на рисунке 7.

Рисунок 7 — Результат работы программы в исключительных ситуациях

Заключение

В процессе выполнения курсового проекта был изучен теоретический материал о бинарных деревьях и их свойствах, разработан алгоритм добавления элементов в упорядоченное двоичное дерево с использованием динамических структур данных и его программная реализация на языке высоко уровня Си. Также данная программа была протестирована в 3 случаях, которые были описаны в экспериментальном разделе.

Список использованных источников

1) Левитин А. В. Алгоритмы: введение в разработку и анализ. — М.: Издательский дом «Вильямс», 2006. — 65 c.

2) Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. — М.: Издательский дом «Вильямс», 2000. — 92 с.

3) Материалы сайта «Программирование на языке C/C++», [Электронный ресурс] - www.procpp.ru.

4) Материалы сайта «Интуит», [Электронный ресурс] - http://www.intuit.ru/.

Приложение I

Листинг программы добавления данных в упорядоченное двоичное дерево:

#include «stdafx.h»

#include «stdlib.h»

#include «conio.h»

#include «locale.h»

void Add (struct binar_tree **current, int data); //добавление

void Show (struct binar_tree *current, int l); //просмотр

void Clear (struct binar_tree **current); //очистка

struct binar_tree

{

int data, count;

binar_tree *left, *right;

};

binar_tree *root = NULL; //корень дерева

int count = 0; //счетчик

int main ()

{

int number, s;

setlocale (LC_ALL, «rus»);

do

{

printf («tМЕНЮ n»);

printf («1.Добавить элемент n»);

printf («2.Просмотр дерева n»);

printf («3.Очистить дерево n»);

printf («0.Выход n»);

printf («Выбранное действие: «);

scanf («%d», &s);

switch (s)

{

case 1:

printf («nВведите элемент: «);

scanf («%d», &number);

Add (&root, number);

printf («nЭлемент добавлен nn»);

printf («—————————————- nn»);

break;

case 2:

if (root≠NULL)

{

printf («n»);

Show (root, 0);

}

else

printf («nДерево пустое nn»);

printf («—————————————- nn»);

break;

case 3:

Clear (&root);

printf («nДерево очищено nn»);

printf («—————————————- nn»);

break;

case 0:

exit (1);

default:

printf («nОшибка!!! nn»);

printf («—————————————- nn»);

break;

}

} while (s ≠ 0);

_getch ();

}

void Add (binar_tree **current, int data)

{

if (*current ≠ NULL)

{

if (data<(*current)->data)

Add (&(*current)->left, data);

else if (data>(*current)->data)

Add (&(*current)->right, data);

else

(*current)->count++;

}

else

{

*current = new binar_tree;

(*current)->data = data;

(*current)->left = NULL;

(*current)->right = NULL;

(*current)->count = 1;

count++;

}

}

void Show (binar_tree *current, int l)

{

if (current ≠ NULL)

{

Show (current->right, l+1);

for (int i=0; i

printf («t»);

printf («%d n», current->data);

Show (current->left, l+1);

}

}

void Clear (binar_tree **current)

{

if (*current ≠ NULL)

{

Clear (&(*current)->left);

Clear (&(*current)->right);

delete *current;

count = count-1;

if (count == 0)

*current = NULL;

}

}