Бинарное дерево поиска

 

       Министерство  образования Российской Федерации

         ГОУВПО «Воронежский  государственный  технический университет» 

Кафедра автоматизированных и вычислительных систем 
 
 
 

Тема 

Бинарное  дерево поиска 
 

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

по  курсовойработе 

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

Программирование на языке высокого уровня 
 
 

                                   Выполнил:

                                   студент ФВЗО гр.ВМ-101 

                                   Гулевский А.В. 
 

                                   Руководитель: Холопкина Л.В. 
 
 
 
 
 
 
 
 

Воронеж 2011

СОДЕРЖАНИЕ: 
 

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

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

РАЗДЕЛ 1 

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

РАЗДЕЛ 2 

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

РАЗДЕЛ 3 

      Рабочая программа, с комментариями…………………………………….12 

РАЗДЕЛ 4 

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

ВЫВОД..………………………………………………….……………………..18 

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

       ВВЕДЕНИЕ 

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

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

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

       Построить бинарное дерево поиска целочисленного типа данных. Выполнить обход дерева   сверху вниз (корень -  левое поддерево – правое поддерево).   При обходе подсчитать:

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

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

       в)  количество вершин, имеющих не более одной ненулевой связи. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

       

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

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

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

       Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2.

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

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

       

 

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

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

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

       

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

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

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

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

       Есть  еще одна разновидность бинарных деревьев, которая называется дерево поиска. Это двоичное дерево организовано так, что для каждой вершины   справедливо утверждение, что все ключи левого поддерева    меньше ключа   , а все ключи правого поддерева больше его, то такое дерево будем называть деревом поиска. В таком дереве легко обнаружить заданный элемент, для этого достаточно, начав с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины.  Дерево поиска для заданной последовательности целых чисел 23, 17, 26,  32,  18,  6,  2,  5,  8,  29,  146 имеет вид:

       

       Рис.4 «Бинарное дерево писка» 
 

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

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

       в прямом порядке 

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

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

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

       Попасть в корень

       Пройти  в прямом порядке левое поддерево 

       Пройти  в прямом порядке правое поддерево  

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

       Пройти  в симметричном порядке левое  поддерево 

       Попасть в корень

       Пройти  в симметричном порядке правое поддерево

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

       Пройти  в обратном порядке левое поддерево 

       Пройти  в обратном порядке правое поддерево 

       Попасть в корень  

       

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

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

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

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

            Применение 

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

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

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

       Для построения такого бинарного дерева используется следующий ссылочный  тип: 

       Type inform = Integer;

       ss = ^zveno;

       zveno = Record

       key: Integer;

       inf: Inform;

       left, right: ss;

       End; 

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

       Var

       t:ss;

       n,nn,c,i,k: Integer; 

       Тогда двоичное дерево можно построить  с помощью следующей процедуры: 

       Procedure Vstavka (Var p: ss; x: Integer);

       Begin

       If p = Nil Then

       Begin

       New (p);

       p^.inf:=x;

       p^.key:=1;

       p^.left:=Nil;

       p^.right:=Nil;

       End

       else begin

       If x<p^.inf Then Begin Vstavka (p^.left,x); End;

       If x>=p^.inf Then Begin Vstavka (p^.right,x); End;

       end;

       End; 

       Существует  три основных способа обхода деревьев: в прямом порядке, обратном и концевом. Обход дерева может быть выполнен рекурсивной процедурой и процедурой без рекурсии (стековый обход). В приведенной ниже рекурсивной процедуре выполняется обход дерева в прямом порядкеи подсчёт для текущего дерева нулевые связи вершин в соответствии с заданием. 

       Function Count(p: ss; v: integer):integer;

       Begin

       { Нет элемента -- результата ноль }

       IF p = Nil Then Count:=0

       ElseBegin

       { Рассматриваются  варианты вызова  функции с соответствующими  условием}

          { Первый вариант  -- либо left, либо right не  равны Nil }

       If ((v = NeMensheOdnoj) and ((p^.left<> Nil) or (p^.right<> Nil)))

       or

          { Второй вариант  -- и left, и right не  равны Nil  }

       ((v = Dve) and ((p^.left<> Nil) and (p^.right<> Nil)))

       or

       { Третий вариант  -- либо left, либо right равны  Nil  }

       ((v = NeBolsheOdnoj) and ((p^.left = Nil) or (p^.right = Nil)))

       { Какой-то из вариантов  сработал => ставим 1

       и добавляем результаты рекурсивных вызовов  левой и правой ветви}