Исследование алгоритма поиска на бинарном дереве

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

Федеральное государственное бюджетное образовательное

Учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФБГОУ ВПО КубГТУ)

 

 

Факультет    компьютерных технологий и автоматизированных систем

Кафедра    информационных систем и программирования

 

 

КУРСОВАЯ РАБОТА

 

 

 

 

 

     по дисциплине                   «Алгоритмы и структура данных»                                  

                       (наименование дисциплины)

     на тему:     Исследование алгоритма поиска на бинарном дереве 1 

                    (тема курсового проекта (работы))

     Выполнил  студент  группы                       13-СМ-231000                                   2    

                                       Дердерян Андрей Аиквич_____________________                                                       

            (ф.и.о.)

     Допущен к  защите_______________________________________________

 

     Руководитель  работы                                                                     О.Б Попова

    

     Защищен _______________________     Оценка _______________________

 

Члены комиссии                                                                                               а

                                                                                                                              А

                                                                                                                              А

                                                                           (подпись, дата, расшифровка подписи)

 

Краснодар

2013

 

 

 

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

Федеральное государственное бюджетное образовательное

Учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФБГОУ ВПО КубГТУ)

 

Факультет    компьютерных технологий и автоматизированных систем

Кафедра    информационных систем и программирования

                 

              УТВЕРЖДАЮ

Зав. кафедрой ИСП                                     1

Профессор                            Л.А.Видовский 

«      »                                                 2013г.

 

ЗАДАНИЕ

на курсовую работу

Студенту:   Дердерян Андрей Аиквич    группы 13-СМ-2310 1 курса

Факультета     МИППС                                                                                            1

Направление     231000      Программная инженерия                                           1

      (шифр и наименование)

Тема проекта:   Исследование алгоритма поиска на бинарном дереве.                             

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

     Объем курсовой  работы:

а) пояснительная записка    16  с.

б) программа.

Рекомендуемая литература: Информатика Программирование (Т.А. Павловская) Практическое программирование. Приемы создания программ на языке Паскаль 1

Срок выполнения проекта: с  «6» апреля  2013г. по «20» мая 2013г.

Срок защиты:                                                         с «20» мая по «25» мая 2013 г.

Дата выдачи задания:                                                                 «6» апреля 2013 г.

Дата сдачи проекта на кафедру:                                                   «25» мая 2013 г.

Руководитель работы ____________________________________ О.Б Попова

                                                                                                                                     (подпись)

Задание принял студент _______________________________ Дердерян А.А.

Реферат

 

 

Пояснительная записка курсовой работе 16 с., 8 рис., 5 источника.

 

ДЕРЕВО, ОБХОД, КОРЕНЬ, УЗЕЛ, ВИДЫ ДЕРЕВЬЕВ, БИНАРНОЕ ДЕРЕВО, ПОИСК В БИНАРНОМ ДЕРЕВЕ, ВИДЫ ОБХОДА, ПРОГРАММИРОВАНИЕ, ЯЗЫКЕ ПРОГРАММИРОВАНИЯ, PASCAL ABC.

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

Цель работы: закрепление основ и углубление знаний в области информатики и программирования, разработка алгоритма обхода дерева, получение дополнительных практических навыков  и приемов работы средствами Pascal ABC.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

 

 
Введение

 

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

Постановка задачи

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

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.Описание интерфейса программы.

 

При запуске программы пользователь увидит форму с полем для ввода количества элементов дерева (Рис.5).

Рис.6 "Рабочее окно программы"

Затем поочередно вводим необходимые данные (Рис.7).

Рис.7 "Ввод данных"

Рис.8 "Вывод результата работы программы на экран"

 

После нажатия Enter программа будет выдавать графическое представление дерева, а также искомые величины. (Рис.8)

 

Заключение

 

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

 

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

 

1. Ахо А.А., Хопкрофт Д.Э., Ульман  Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007.

2. Бежанова М. М, Москвина Л.А. Практическое програмирование. Приемы создания программ на языке Паскаль. М. Научный Мир. 2000. - 270 с.

3. Подвальный С.Л., Холопкина Л.В., Носачева М.П. Программирование на языке паскаль: практикум. Воронеж. ГОУВПО ВГТУ. 2008.

4. Информация с Веб-сайта http://www.lib. csu.ru.

5. Информация с Веб-сайта http://algolist. manual.ru/sort/pyramid_sort. php; кому нужны исходники - стучитесь - lexmod@mail.ru денег не беру))

 

Приложение А

 

Листинг программы:

Program Binar_derevo;

Uses Crt;

{Варианты запуска  обхода с подсчетом:

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

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

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

Const NeMensheOdnoj=1;

Dve=2;

NeBolsheOdnoj=3;

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;

{----вывод дерева----}

Procedure Print (Var p: ss; h: Integer);

Var i: Integer;

Begin

If p <> Nil Then

Begin

Print (p^. right,h+4);

For i: =1 To h Do Write (' ');

Writeln (p^. inf);

Print (p^. left,h+4);

End;

End;

{ Рекурсивная  функция, делающая подсчёт для  текущего дерева }

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