Во-вторых, если полное дерево порядка D состоит  из N узлов, оно будет иметь высоту порядка O(log_D(N)) и O(N) листьев. Эти факты имеют большое значение, поскольку многие алгоритмы обходят деревья сверху вниз или в противоположном направлении. Время выполнения алгоритма, выполняющего одно из этих действий, будет порядка O(N).

     Чрезвычайно полезное свойство полных деревьев заключается  в том, что они могут быть очень компактно записаны в массивах. Если пронумеровать узлы в «естественном» порядке, сверху вниз и слева направо, то можно поместить элементы дерева в массив в этом порядке.

     Последовательное  обращение ко всем узлам называется обходом (traversing) дерева. Существует несколько последовательностей обхода узлов двоичного дерева. Три простейших из них — прямой (preorder), симметричный (inorder), и обратный (postorder)обход, описываются простыми рекурсивными алгоритмами. Для каждого заданного узла алгоритмы выполняют следующие действия:

     Прямой  обход:

1) обращение  к узлу;

2. рекурсивный прямой обход левого поддерева;
3. рекурсивный прямой обход правого поддерева.

     Симметричный  обход:

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

     2) обращение к узлу;

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

     Обратный  обход:

1) рекурсивный  обратный обход левого поддерева;

2) рекурсивный  обратный обход правого поддерева;

3) обращение  к узлу.

     Все три порядка обхода являются примерами обхода в глубину (depth-first traversal). Обход начинается с прохода вглубь дерева до тех пор, пока алгоритм не достигнет листьев. При возврате из рекурсивного вызова подпрограммы, алгоритм перемещается по дереву в обратном направлении, просматривая пути, которые он пропустил при движении вниз.

     Четвертый метод перебора узлов дерева — это обход в ширину (breadth-first traversal). Этот метод обращается ко всем узлам на заданном уровне дерева, перед тем, как перейти к более глубоким уровням. Алгоритмы, которые проводят полный поиск по дереву, часто используют обход в ширину.

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

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

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

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

     Если  в определении дерева снять единственность корня, то получим лес. Вырожденное дерево – дерево с одним листом, и каждый нелистовой узел имеет 1 сына. Такое дерево эквивалентно связанному списку.

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

2 ПОСТАНОВКА  ЗАДАЧИ

 

     2.1 Общая постановка задачи 

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

      В целом, ДП должна обладать следующими возможностями:

1. теоретические сведения о двоичных деревьях;
2. создание бинарного дерева;
3. добавление элементов в дерево, учитывая ограничение в два символа (для избежания выхода символов за графический предел прорисовки) и проверку на существование подобного элемента;
4. удаление элементов из дерева, учитывая существование такового;
5. построение дерева;
6. осуществление поиска заданного элемента.

     Данная  программа может быть использована в качестве наглядного пособия при изучении раздела: «Двоичные деревья» для курса: «Структуры и организация данных в ЭВМ». 

      2.2 Схема информационных потоков 

     Схема, определяющая потоки входных данных, поступающих с устройств ввода в программу и поток выходных данных, поступающих на устройство вывода, представлены на рисунке 2.1.

 
 
 

Рисунок 2.1 – Схема информационных потоков

 

     Программой  не предусмотрен ввод исходного дерева из файла и вывод результата в  файл.

 

3 Описание входных  и выходных структур  данных

      3.1 Входные данные

 

     Входными  данными являются натуральные числа, принадлежащие диапазону {-9,…,99}. Размер каждого элемента ограничен до двух знаков во избежание затруднений при визуализации БД.

     Поступать данные могут только с клавиатуры.

3.2 Выходные данные

 

     Выходными данными является сформированное БД.

     В процессе работы с БД изменяется его  структура, что автоматически отображается на экране.

 

4 Описание и обоснование  выбора метода  решения и алгоритмы

 

     4.1 Обоснование выбора языка программирования 

     Для реализации программы был выбран язык программирования С как один из самых быстрых и эффективных.

      Следует также отметить, что язык С является языком высокого уровня, а писать программы  на таких языках и отлаживать эти программы значительно проще по сравнению с низкоуровневыми языками (например, Basic, Assembler). 

     4.2 Структура для узла в языке  С 

     Просмотрев  еще раз определение узла, можно  написать на языке С определение аналогичной структуры, приведённое на рисунке 4.1. 

     struct bin_node {

           int data;

     struct bin_node *left;

     struct bin_node *right;

     };

     Рисунок 4.1 – Структура для узла 

     Нужно обратить внимание на точное соответствие абстрактного определения двоичного дерева и структуры, создаваемой в этом листинге:                  struct bin_node содержит значение data, указатель на левое поддерево – left и указатель на правое поддерево – right.

     Для демонстрационных целей значение узла будет иметь тип int. 

     4.3 Структура в языке С для  дерева 

     Кроме отслеживания отдельных узлов, необходимо иметь возможность работы со всем деревом. В большинстве случаев эта задача сводиться к отслеживанию корневого узла дерева, что позволяет легко передать это дерево для обработки функциям. Но иногда бывает необходимо хранить и другую информацию о дереве. С этой целью проще всего определить ещё одну структуру для самого дерева и поместить в неё указатель на его корень и дополнительную информацию(см. Рисунок 4.2). 

     struct bin_tree {

           struct bin_node *root;

           int count;

     };

     Рисунок 4.2 – Структура для дерева 

     Здесь переменная root определена как указатель на узел. Данную переменную можно было бы объявить как сам узел, но это усложнило бы некоторые операции. Вообще, корень легче объявить как указатель.

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

     4.4 Создание БД 

     Создать пустое двоичное дерево очень просто. Прежде всего необходимо с помощью функции malloc() выделить память под структуру struct bin_tree. Если функция malloc() завершиться неудачно, вызывающей программе в качестве предупреждения будет возвращён нулевой указатель. Если выделение памяти прошло успешно, инициализируется новое дерево и вызывающей программе возвращается указатель на это дерево. 

     4.5 Поиск 

     Само  по себе двоичное дерево бесполезно. Теперь необходимо наполнить его данными. Оказывается, что первым шагом при  вставке узла (и при многих других операциях с БД) является поиск узла с таким же значением (см. Рису-нок 4.3). 

     int bin_search(const struct bin_tree *tree, int item)

     {

           const struct bin_node *node;

           assert(tree != NULL);

     node = tree->root;

           for(;;) {

                 if (node == NULL)

                       return 0;

                 else if (item == node->data)

                       return 1;

                 else if (item > node->data)

                       node = node->right;

                 else

                       node = node->left;

           }

     }

     Рисунок 4.3 – Поиск 

     Здесь я объявил функцию bin_search(), которая будет осуществлять поиск значения item по дереву tree. Если значение item присутствует в дереве, эта функция возвращает ненулевое значение, если же такого значения нет, функция возвращает нуль.

     Функция bin_search() начинает свою работу с проверки аргументов. Это очень важный момент, особенно для функций, которые делают определённые предположения о своих аргументах (т.е. практически для всех функций). В моём примере необходимо убедиться, что tree является структурой bin_tree. Хотя и нельзя точно это проверить, тем не менее, можно проверить, не является ли tree просто нулевым указателем.

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

     Если  значение item больше значения узла, то оно должно находиться в правом поддереве (если оно вообще есть в дереве), поэтому мы переходим в правое поддерево и повторяем весь процесс. Если значение item меньше значения узла, то оно должно находиться в левом поддереве, поэтому мы переходим в левое поддерево и опять повторяем весь процесс.

     Рассмотрим  поведение функции bin_search() для предельного случая, когда дерево пустое. Всегда есть смысл проверять поведение программ в таких граничных случаях, поскольку потом возникают ошибки. Как бы то ни было, в моём примере ошибки не будет: если дерево tree пустое, то tree->root будет нулевым указателем и функция bin_search() возвратит 0 при первом же проходе цикла.