Многие алгоритмы, использующие бинарные деревья, включают два этапа. На первом этапе строится бинарное дерево, а на втором выполняется систематический обход его вершин. Наиболее часто используются следующие способы обхода вершин дерева:
1) Обход в прямом порядке (просмотр в глубину).
2) Обход в обратном порядке.
3) Симметричный обход (обход во внутреннем порядке).
Все три способа описываются рекурсивными алгоритмами.
Бинарное дерево схематически можно представить следующим образом:
T – выделенная вершина – корень, L – левое поддерево, R – правое поддерево.
Тогда для прямого обхода используется алгоритм TLR. Он включает следующие шаги:
1) просмотр корня T
2) просмотр с помощью алгоритма TLR левого поддерева
3) просмотр с помощью алгоритма TLR правого поддерева
Обход в обратном порядке реализуется с помощью алгоритма LRT:
1) обход левого поддерева с помощью алгоритма LRT
2) обход правого поддерева с помощью алгоритма LRT
3) просмотр корня T
Симметричный обход реализуется с помощью алгоритма LTR:
1) просмотр левого поддерева с помощью алгоритма LTR
2) просмотр корня T
3) просмотр правого поддерева с помощью алгоритма LTR
Пример:
Прямой порядок: TLR: 1,2,4,5,8,9,3,6,10,7.
Обратный порядок: LRT: 4,8,9,5,2,10,6,7,3,1.
Симметричный порядок: LTR: 4,2,8,5,9,1,6,10,3,7.
Рассмотрим реализацию этих алгоритмов в программах. Пусть соответствующая процедура обхода вершин некоторого дерева T печатает метки этих вершин. INFO(i,T).
p – указатель на корень дерева
q – указатель на другую вершину
LEFT(i,T) – определение левого потомка вершины i в дереве T.
RIGHT(i,T) – определение правого потомка вершины i в дереве T.
Функции возвращают номер вершины.
INFO(i,T) – возвращает информацию, приписанную вершине i дерева T.
Procedure TLR (p:position);
Var q:position;
Begin
If p<>NIL then
Begin
write(INFO(p,T));
q:=LEFT(p,T); TLR(q);
q:=RIGHT(p,T); TLR(q);
end;
end;
Procedure LRT (p:position);
Var q:position;
Begin
If p<>NIL then
Begin
q:=LEFT(p,T); LRT(q); q:=RIGHT(p,T); LRT(q);
write(INFO(p,T));
end;
end;
Procedure LTR (p:position);
Var q:position;
Begin
If p<>NIL then
Begin
q:=LEFT(p,T); LTR(q); write(INFO(p,T));
q:=RIGHT(p,T); LTR(q); end;
end;
|
Главная
Каталог файлов
