Файл: Динамические структуры данных. Бинарные деревья..pdf

left,right : PNode;

end;

значений элементов. в виде , значение полей . Тривиальным , когда – пустой, и, , не информационного .

function Sum(Root : PNode) : integer;

begin

if Root=Nil then {узел - пустой}

Sum := 0

else

Sum := Root^.Data + Sum(Root^.left)

+ Sum(Root^.right);

{end if}

end;

Для случая как значение в корне () суммы левого и .

А выражение рекурсивный поддерева для Root.

А2. Подсчет количества узлов в бинарном дереве

function NumElem(Tree:PNode):integer;

begin

if Tree = Nil then

NumElem := 0

else

NumElem := NumElem(Tree^.left)+ NumElem(Tree^.right) + 1;

end;

Подсчет количества листьев бинарного дерева

function Number(Tree:PNode):integer;

begin

if Tree = Nil then

Number := 0 {дерево пустое - листов нет}

else if (Tree^.left=Nil) and (Tree^.right=Nil) then

Number := 1 {дерево состоит из одного узла - листа}

else

Number := Number(Tree^.left) + Number(Tree^.right);

{end if}

end;

Анализ приведенных алгоритмов показывает, что для получения ответа в них производится просмотр всех узлов дерева. Ниже будут приведены алгоритмы, в которых порядок обхода узлов дерева отличается. И в зависимости от порядка обхода узлов бинарного упорядоченного дерева, можно получить различные результаты, не меняя их размещения.

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

Алгоритмы просмотра дерева

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

Прежде чем увидеть, к каким результатам это может привести, приведем

их.

Просмотр дерева слева – направо

procedure ViewLR(Root:PNode); {LR -> Left - Right }

begin

if Root<>Nil then

begin

ViewLR(Root^. left); {просмотр левого поддерева}

{Операция обработки корневого элемента - вывод на печать, в файл и др.}

ViewLR(Root^.right); { просмотр правого поддерева }

end;

end;

Просмотр справа налево

procedure ViewRL(Root:PNode); {LR -> Right - Left}

begin

if Root<>Nil then

begin

ViewRL(Root^.right); { правого }ViewRL(Root^.left); { левого }

end;

end;

Просмотр сверху - вниз

procedure ViewTD(Root:PNode); {TD -> Top-Down}

begin

if Root<>Nil then

begin

Операция обработки корневого элемента - вывод на печать, в файл и др.

---

ViewTD(Root^.left); {просмотр левого поддерева}

ViewTD(Root^.right); { просмотр правого поддерева }

end;

end;

Просмотр снизу-вверх

procedure ViewDT(Root:PNode); {DT -> Down - Top}

begin

if Root<>Nil then

begin

ViewDT(Root^.left); {просмотр левого поддерева}

ViewDT(Root^.right); { просмотр правого поддерева }

end;

end;

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

function Search(SearchValue:integer;Root:PNode):PNode;

begin

if (Root=Nil) or (Root^.Data=SearchValue) then

Search := Root

else if (Root^.Data > SearchValue) then

Search := Search(SearchValue,Root^.left)

else

Search := Search(SearchValue,Root^.right);

end;

2.2 Текст программы бинарное дерево динамический алгоритм

type link = ^element;

element = record

data : integer;

left : link;

right : link;

end;

var

m,x, depth, minim : integer;

pn : link;

procedure add(var n : link; arg:integer);

var

ind, neo : link;

begin

new(neo);

neo^.data:=arg;

neo^.left:=nil;

neo^.right:=nil;

if n=nil then n:= neo

else begin

ind:=n;

while neo<>nil do begin

if arg<ind^.data then begin

if ind^.left=nil then begin

ind^.left:=neo;

neo:=nil

end

else ind:=ind^.left

end

else

if arg>ind^.data then begin

if ind^.right=nil then begin

ind^.right:=neo;

neo:=nil

end

else ind:=ind^.right

end

else begin

writeln('Such element is already existent');

neo:=nil;

end;

end;

end;

end; { add }

procedure restruct(var d : link);

var

ind1, ind2 : link;

begin

ind1:=d;

if ind1^.right=nil then begin

ind2:=d;

d:=ind2^.left;

dispose(ind2)

end

else

if ind1^.left=nil then begin

ind2:=d;

d:=ind2^.right;

dispose(ind2)

end

else begin

ind2:=ind1^.left;

while ind2^.right<>nil do begin

ind1:=ind2;

ind2:=ind2^.right;

end;

ind1^.right:=ind2^.left;

ind2^.left:=d^.left;

ind2^.right:=d^.right;

dispose(d);

d:=ind2;

end;

end; { restruct }

procedure delete(var n : link; arg:integer);

var

del, ind : link;

t : boolean;

begin

t:=false;

del:=n;

while (del<>nil) and (not t) do begin

if arg=del^.data then t:=true

else

if arg<del^.data then begin

ind:=del;

del:=del^.left;

end

else begin

ind:=del;

del:=del^.right;

end;

end;

if t then begin

if (del^.left=nil) and (del^.right=nil) then begin

if del=n then begin n:=nil; dispose(del) end else

if ind^.left=del then begin

ind^.left:=nil;

dispose(del)

end

else begin

ind^.right:=nil;

dispose(del)

end

end

else

if del=n then restruct(n) else

if ind^.left=del then restruct(ind^.left)

else restruct(ind^.right)

end

else writeln('Element is absent');

end; { delete }

procedure view( n : link; var d:integer);

var

i : integer;

begin

for i:=1 to d do begin

write(' ') end;

writeln(n^.data);

if (n^.left=nil) and (n^.right=nil) then d:=d-1

else begin

if n^.right<>nil then begin

d:=d+1;

view(n^.right,d);

end;

if n^.left<>nil then begin

d:=d+1;

view(n^.left, d);

end;

d:=d-1;

end;

end; { view }

procedure obhod1( n : link; var d, min:integer);

---

begin

if (n^.left=nil) and (n^.right=nil) then begin

if d<min then min:=d;

d:=d-1 end

else begin

if n^.right<>nil then begin

d:=d+1;

obhod1(n^.right, d, min); end;

if n^.left<>nil then begin

d:=d+1;

obhod1(n^.left, d,min) end;

d:=d-1;

end;

end; { obhod1 }

procedure obhod2( n : link; var d:integer; min:integer);

begin

if (n^.left=nil) and (n^.right=nil) then begin

if d=min then writeln(n^.data);

d:=d-1;

end

else begin

if n^.right<>nil then begin

d:=d+1;

obhod2(n^.right,d,min);

end;

if n^.left<>nil then begin

d:=d+1;

obhod2(n^.left, d,min);

end;

d:=d-1;

end;

end; { obhod2 }

begin

m:=1;

pn:=nil;

while m<>0 do begin

writeln;

writeln('--- Type "1" to ADD new element');

writeln('--- Type "2" to DELETE element');

writeln('--- Type "3" to VIEW tree');

writeln('--- Type "4" to FIND elements with minimal depth');

writeln('--- Type "0" to EXIT program');

writeln;

write('Enter : ');

readln(m);

writeln;

case m of

1 : begin

write('Enter new element : ');

readln(x);

add(pn, x);

end;

2 : begin

write('Enter element you want to delete : ');

readln(x);

delete(pn, x);

end;

3 : begin

depth:=1;

if pn=nil then writeln('The tree is empty') else begin

writeln('The tree is : ');

view(pn, depth);

end;

end;

4 : begin

depth:=1;

minim:=20;

if pn<>nil then begin

writeln('Elements with minimal depth');

obhod1(pn,depth,minim);

writeln(minim);

depth:=1;

obhod2(pn,depth,minim);

end

else writeln('The tree is empty');

end;

end; { case }

end;

Заключение

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

Нами выявлено, что дерево является структурой данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.

Деревья особенно часто используют на практике при изображении различных иерархий.

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

---

Библиографический список

1. Н. Вирт. Алгоритмы и структуры данных: пер. с англ. / Н.Вирт. Изд. 2-е, испр. – СПб.: Невский диалект, 2005. – 352 с.

2. Ахо А. Структуры данных и алгоритмы: пер. с англ. / А.Ахо, Д. Хопкрофт, Д.Ульман. – М.: Вильямс, 2016. – 400 с.

3. Уильям Топп, Уильяи Форд. Структуры данных в С++: Пер. с англ. – М. ЗАО «Издательство БИНОМ», 1999. – 816 с.

4. Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов / Т.А.Павловская. – Спб.: Питер, 2014. – 432 с.

5. Фаронов В.В. Создание приложений с помощью C#. Руководство программиста / В.В. Фаронов. – М.: Эксмо, 2008. – 576 с.

6. Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с.

7. Шилдт, Герберт. C# 3.0: руководство для начинающих: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2009. – 688 с.

8. Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с.

9. Гросс, Кристиан. C# 2008 и платформа NET 3.5 Framework: базовое руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2009. – 480 с.

10.Петцольд, Чарльз. Программирование для Microsoft Windows 8. Пер. с англ. – СпБ.: Издательский дом «Питер», 2014. – 1008 с. 31

11.Стиллмен, Эндрю, Грин, Дженнифер. Изучаем C#. Пер. с англ. – СпБ.: Издательский дом «Питер», 2017. – 816 с.

12.Кнут Д. Искусство программирования для ЭВМ: в 3 т. Т 1: пер. с англ. / Д.Кнут. – М.: Вильямс, 2000. – 720 с.

1. Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов / Т.А.Павловская. – Спб.: Питер, 2014. – 432 с. ↑

2. Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑

3. Петцольд, Чарльз. Программирование для Microsoft Windows 8. Пер. с англ. – СпБ.: Издательский дом «Питер», 2014. – 1008 с. 31 ↑

4. Кнут Д. Искусство программирования для ЭВМ: в 3 т. Т 1: пер. с англ. / Д.Кнут. – М.: Вильямс, 2000. – 720 с. ↑

5. Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑

6. Стиллмен, Эндрю, Грин, Дженнифер. Изучаем C#. Пер. с англ. – СпБ.: Издательский дом «Питер», 2017. – 816 с. ↑

7. Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов / Т.А.Павловская. – Спб.: Питер, 2014. – 432 с. ↑

8. Ахо А. Структуры данных и алгоритмы: пер. с англ. / А.Ахо, Д. Хопкрофт, Д.Ульман. – М.: Вильямс, 2016. – 400 с. ↑

9. Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑

10. Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑

11. Н. Вирт. Алгоритмы и структуры данных: пер. с англ. / Н.Вирт. Изд. 2-е, испр. – СПб.: Невский диалект, 2005. – 352 с. ↑

12. Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑

13. Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑

---