Добавлен: 29.03.2023
Просмотров: 103
Скачиваний: 2
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 с.
-
Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов / Т.А.Павловская. – Спб.: Питер, 2014. – 432 с. ↑
-
Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑
-
Петцольд, Чарльз. Программирование для Microsoft Windows 8. Пер. с англ. – СпБ.: Издательский дом «Питер», 2014. – 1008 с. 31 ↑
-
Кнут Д. Искусство программирования для ЭВМ: в 3 т. Т 1: пер. с англ. / Д.Кнут. – М.: Вильямс, 2000. – 720 с. ↑
-
Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑
-
Стиллмен, Эндрю, Грин, Дженнифер. Изучаем C#. Пер. с англ. – СпБ.: Издательский дом «Питер», 2017. – 816 с. ↑
-
Павловская Т.А. C#. Программирование на языке высокого уровня: учебник для вузов / Т.А.Павловская. – Спб.: Питер, 2014. – 432 с. ↑
-
Ахо А. Структуры данных и алгоритмы: пер. с англ. / А.Ахо, Д. Хопкрофт, Д.Ульман. – М.: Вильямс, 2016. – 400 с. ↑
-
Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑
-
Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑
-
Н. Вирт. Алгоритмы и структуры данных: пер. с англ. / Н.Вирт. Изд. 2-е, испр. – СПб.: Невский диалект, 2005. – 352 с. ↑
-
Биллиг В.А.Основы программирования на C#: учебное пособие / В.А.Биллиг – М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2009. – 483 с. ↑
-
Шилдт, Герберт. С# 4.0: Полное руководство: Пер. с англ. – М.: Издательский дом «Вильямс», 2011. – 1056 с. ↑