Бинарное упорядоченное дерево

     1. Добавление элемента. Добавляем узел слева, если его значение менше значения текущего элемента и добавляем его справа, если больше.

 
 
 

                            Да                                         Нет 

 
 

Нет

      Нет

                Да

 

 
 
 
 
 

Рис. 2.1 «Алгоритм добавления нового элемента в дерево»

     2.Удаление элемента. Если узел – лист, просто удаляем его, если узел имеет одного потомка, заменяем узел им, если же узел имеет двух потомков, то реализуется алгоритм, представленный на Рис.2.2, который заменяет удаляемый узел самым правым потомком его левого поддерева. 
 
 

                                                                                                              

                                                                                                              Да 

                                                                                 

                                                                                Нет

 

 
 

Рис. 2.2 «Алгоритм удаления узла, имеющего двух потомков» 
 
 
 
 
 

  да

                    

                                           Нет

                                                                  

 Да 

                                                                              Нет

                                                                                        

                                                                                                

 Да

      Нет

                                                   Да                    

      Нет 

                                                                                                              Да

                                             

            Нет

                                                                                                                                                              

                                                            

 
 

Рис. 2.3 «Алгоритм удаления узла из дерева»

     3.Поиск одинаковых элементов. Сперва записываем все элементы дерева в строку, а затем реализуем алгоритм поиска одинаковых элементов в данной строке.

 

 
 

          Да

    

                                                                                         Нет 

                                                                                           
 

                                                                                          Да

 Да Нет

  

                                                                 

Рис.2.4 «Поиск одинаковых элементов в дереве»

            4.Нахождение длины пути от корня до заданной вершины.  Ищем заданный элемент в дереве, увеличивая «счетчик уровня» на 1 при каждом переходе к потомку узла. 

 

                                 Да                                                                               Нет                                                                 

 

   Да 

                         Нет

 

                                                           Да

 

                                       

 Нет

 

 

                                                                                                             

 

Рис. 2.5 «Алгоритм нахождения длины пути от корня до заданной вершины»

РАЗДЕЛ 3.Техническое задание

     3.1.Основание  для разработки.

     Основанием  для выполнения данной курсовой работы является учебный план по дисциплине «Модели и структуры данных» ХГТУСА.

     3.2.Назначение разработки.

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

     3.3.Требования к программному обеспечению.

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

     б) время ответа <=1 секунды;

     в) тип операционной системы: Windows 98/2000/XP;

     г) для запуска программы требуется Borland Delphi 7, каких-либо дополнительных приложений для своей работы программа не требует;

     д) процессор Pentium  или Celeron с тактовой частотой не ниже 166 МГц, оперативной памяти 256 Мбайт;

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

     3.4. Этапы разработки.

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

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

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

     г) реализация уже готовых алгоритмов на языке программирования Delphi, создание программы;

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

РАЗДЕЛ 4. Описание программы 

4.1.Описание программного обеспечения

       В программе основным элементом является созданный класс TTree. Его методы – это основные процедуры работы с деревом:

       Create – конструктор класса – процедура, инициализирующая дерево;

       Add – метод добавления элемента в дерево;

       Del – метод удаления элемента из дерева;

       Prosmotr – метод вывода элементов дерева на экран;

       Find – метод поиска длины пути от корня до заданной вершины;

       Check – метод проверки дерева на наличие одинаковых элементов;

       Destroy – деструктор класса – процедура, удаляющая дерево. 

       Рассмотрим  алгоритмы работы процедур. 

       Create – инициализация дерева. Присваивает полю Root (корень) значение nil – указателя, который никуда не указывает. 

       Add – добавление элемента в дерево. Для построения дерева используем следующий алгоритм. Первый элемент помещаем в корень. Далее поступаем следующим образом. Если добавляемый в дерево элемент имеет ключ больший, чем ключ узла, то, если узел не лист, обходим его справа. Если добавляемый элемент имеет ключ не больший чем ключ узла, то, если узел не лист, обходим его слева. Если дошли до листа, то добавляем элемент соответственно справа или слева. Блок-схема данной процедуры показана на Рис. 3.1.1. 
 

                           

                      Да                                  Нет 
 
 

      Нет

                                                                                                     Да

 

 

 

 

       Рис. 4.1.1 «Блок-схема процедуры Add, добавляющей новый элемент» 

       Del – удаление элемента из дерева.

       Удаление  узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла К на указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления. 
 

       

       Например, если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно на К и R, что не возможно. В этом случае удаляемый узел нужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом его заменить? Этот узел должен обладать двумя свойствами: во-первых, он должен иметь не более одного потомка; во-вторых, для сохранения упорядоченности ключей, он должен иметь ключ либо не меньший, чем любой ключ левого поддерева удаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемого узла. Таким свойствам обладают два узла, самый правый узел левого поддерева удаляемого узла и самый левый узел его правого поддерева. Любым из этих узлов можно заменить удаляемый узел. Например, на рисунке это узлы М и Р.