Дерево. Пояснительная записка по курсовой работе Тема Бинарное дерево поиска по дисциплине Программирование на языке высокого уровня Гулевский А. В

• Название: Пояснительная записка по курсовой работе Тема Бинарное дерево поиска по дисциплине Программирование на языке высокого уровня Гулевский А. В
• Анкор: Дерево
• Дата: 09.02.2022
• Размер: 2.56 Mb.
• Имя файла: 129562.rtf
• Тип: Пояснительная записка; #356018

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

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

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


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

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

Тема

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

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

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


Выполнил: Гулевский А.В.

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

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

Воронеж 2011
Содержание

Введение 3

Раздел 1. Общие сведения о бинарных деревьях 4

Раздел 2. Алгоритмическая часть 8

Раздел 3. Рабочая программа, с комментариями 11

Раздел 4. Описание интерфейса программы 15

Выводы 17

Список использованной литературы 18

Введение

В данной курсовой работе разработана программа для работы с бинарным упорядоченным деревом. Программа была создана в среде 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


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

Else Begin

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

{ Первый вариант - либо 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

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

Then Count: =1 + Count (p^. left,v) + Count (p^. right,v)

{ Иначе берём 0 и добавляем рекурсивные вызовы }

else Count: =0 + Count (p^. left,v) + Count (p^. right,v)

End;

End;
В процедуру встроен счетчик Count, который по окончании работы программы выдает искомый результат.

Раздел 3. Рабочая программа, с комментариями

Program 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


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;

Begin

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

IF p = Nil Then Count: =0

Else Begin

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

{ Первый вариант - либо 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

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

Then Count: =1 + Count (p^. left,v) + Count (p^. right,v)

{ Иначе берём 0 и добавляем рекурсивные вызовы }

else Count: =0 + Count (p^. left,v) + Count (p^. right,v)

End;

End;

{----обходдерева----}

Begin ClrScr;

Writeln ('Vvedite koli4estvo elementov dereva: ');

Readln (n);

randomize;

For i: =1 To n Do

Begin

Writeln ('Vvedite o4erednoj element');

Read (c);

Vstavka (t,c);

End;

Print (t,0);

Writeln ('Koli4estvo vershin c >= 1 nenulevoj svjazi: ',Count (t,NeMensheOdnoj));

Writeln ('Koli4estvo vershin c 2 nenulevymi svjazjami: ',Count (t,Dve));

Writeln ('Koli4estvo vershin c <= 1 nenulevoj svjazi: ',Count (t,NeBolsheOdnoj));

Readkey;

End.

Раздел 4. Описание интерфейса программы

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


Рис.5 "Рабочее окно программы"
Затем поочередно вводим необходимые данные (Рис.6).


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


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

Выводы

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

Список использованной литературы

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

2. Беллман Р. Динамическое программирование. M. ИЛ, 1960.

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

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

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

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