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

Министерство  образования и науки Украины

Харьковский государственный университет строительства  и архитектуры

Кафедра компьютерного моделирования и информационных технологий 
 
 

ТЕМА

БИНАРНОЕ  УПОРЯДОЧЕННОЕ ДЕРЕВО 
 

Пояснительная записка

 по  курсовому проекту

по дисциплине

МОДЕЛИ  И СТРУКТУРЫ ДАННЫХ 
 
 
 
 

                                                                                         Выполнила: Чернышева М.,

                                                                                         студентка гр.ЭКБ-22

                                                                                        Руководитель: Литвиненко Е.Н. 

Харьков 2009

СОДЕРЖАНИЕ: 

ВВЕДЕНИЕ……………………………………………………………………….3

ПОСТАНОВКА ЗАДАЧИ……………………………………………………….4

РАЗДЕЛ 1

      Общие сведения о бинарных деревьях……………………………………..5

РАЗДЕЛ 2

       Алгоритмическая часть…………………………………………………….11

РАЗДЕЛ 3

       Техническое задание……………………………………………………….16

РАЗДЕЛ 4

       Описание программы

          3.1.Описание программного обеспечения……………………………...17

          3.1.Описание интерфейса программы…………………………………..25

ВЫВОДЫ………………………………………………………………………..26

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……………………………27

ПРИЛОЖЕНИЕ А………………………………………………………………28 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 

     В данной курсовой работе разработана программа для работы с бинарным упорядоченным деревом. Программа была создана в среде Borland Delphi 7.

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

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

       Написать программу создания, вывода и обработки бинарного дерева Т, которая выполняет следующие функции:

      а)  определяет, есть ли в дереве Т хотя бы два одинаковых элемента;

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

РАЗДЕЛ 1.Общие сведения о бинарных деревьях 

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

 

                                               

                                                                                     
 

 
 
 
 
 

Рис.1.1 «Пример бинарного дерева»

      
                На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из девяти узлов, А-корень дерева. Его левое поддерево имеет корень В, а правое- корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и I имеют пустые левые и правые поддеревья.

            Если А - корень бинарного дерева и В - корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А. Узел, не имеющий сыновей (такие как узлы D, G, Н и I), называется листом.

            Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2. Например, в дереве из рисунке А-предок G и Н-потомок С, но Е не является ни предком, ни потомком С.

            Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

            Два узла являются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным деревом. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов. Пример строго бинарного дерева приведен на рисунке ниже. 
 

 
 
 
 
 
 
 
 

Рис.1.2 «Строго бинарное дерево» 

            Уровень узла в бинарном дереве  может быть определен следующим  образом. Корень дерева имеет  уровень 0, и уровень любого  другого узла дерева имеет  уровень на 1 больше уровня своего  отца. Например, в бинарном дереве на первом рисунке узел Е- узел уровня 2, а узел Н-уровня 3. Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева. Стало быть, глубина дерева на первом рисунке равна 3.

            Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья. На  рисунке приведен пример полного бинарного дерева уровня 3. 
 

 
 
 
 
 
 

Рис.1.3 «Полное бинарное дерево» 

            Почти полное бинарное дерево - это бинарное дерево, для которого существует неотрицательное целое k такое, что:

     1. Каждый лист в дереве имеет  уровень k или k+1.

     2. Если узел дерева имеет правого  потомка уровня k+1, тогда все его  левые потомки, являющиеся листами, также имеют уровень k+1.

     Есть  еще одна разновидность бинарных деревьев, которая называется упорядоченные  бинарные деревья.

     Упорядоченные бинарные деревья - это деревья, в которых для каждого узла Х выполняется правило: в левом поддереве - ключи, меньшие Х, в правом поддереве - большие или равные Х. Структура бинарного дерева построена из узлов. Узел дерева содержит поле данных и два поля с указателями. 
 

Начало поиска места

Для записи с ключом «12»

                              указатель корня

 

  

           Сюда будет включена запись «12» 

Рис.1.4 «Упорядоченное бинарное дерево»

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

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

Существует 3 способа  обхода бинарного дерева.

1. в прямом порядке
2. в симметричном порядке
3. в обратном порядке

 

В прямом порядке:

1. Попасть в корень
2. Пройти в прямом порядке левое поддерево
3. Пройти в прямом порядке правое поддерево

 

В симметричном порядке:

1. Пройти в симметричном порядке левое поддерево
2. Попасть в корень
3. Пройти в симметричном порядке правое поддерево

 

В обратном порядке:

1. Пройти в обратном порядке левое поддерево
2. Пройти в обратном порядке правое поддерево
3. Попасть в корень

 
 
 

 
 
 
 
 
 
 
 

Прямой порядок:   ABDGCEHIF

Симметричный  порядок:   DGBAHEICF

Обратный порядок:   GDBHIEFCA 

Рис.1.5.

 «Пример  обхода бинарного дерева разными  способами» 

     Применение

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

РАЗДЕЛ 2.Алгоритмическая  часть

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