Структуры и алгоритмы обработки данных. Ключарев А.А - 58 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

58
– при прохождении в симметричном порядке сначала посещаются в
симметричном порядке вершины поддерева Tree
1
, далее корень n, затем
последовательно в симметричном порядке вершины поддеревьев Tree
2
,
…, Tree
k
.
Далее приведены наброски процедур, реализующих указанные спо-
собы обходов деревьев. При доработке этих набросков необходимо учи-
тывать конкретную реализацию деревьев:
procedure PreOrder(n: вершина);
{Обход дерева в прямом порядке}
begin
Занести в список обхода вершину n;
for для каждого потомка s вершины n в порядке слева направо do
PreOrder(s);
end;
procedure LastOrder(n: вершина);
{Обход дерева в обратном порядке}
begin
for для каждого потомка s вершины n в порядке слева направо do
LastOrder(s);
Занести в список обхода вершину n;
end;
procedure InOrder(n: вершина);
{Обход дерева в симметричном порядке}
begin
if n – лист then begin
занести в список обхода узел n;
end else begin
InOrder(самый левый потомок вершины n);
Занести в список обхода вершину n;
for для каждого потомка s вершины n, исключая самый левый,
в порядке слева направо do
InOrder(s);
end;
end;
1.3.4.3. Спецификация двоичных деревьев
Как уже говорилось выше, двоичные (бинарные) деревья – это дере-
вья со степенью не более двух (рис. 16).
По степени вершин двоичные деревья бывают:

Страницы