9. Алгоритмы обхода бинарных деревьев и их применение в трансляции программ и обработке данных
Многие алгоритмы, использующие бинарные деревья, включают два этапа. На первом этапе строится бинарное дерево, а на втором выполняется систематический обход его вершин. Наиболее часто используются следующие алгоритмы обхода вершин бинарного дерева:
Обход в прямом порядке (просмотр в глубину).
Обход в обратном порядке.
Симметричный обход (обход во внутреннем порядке).
Все три алгоритма задаются рекурсивными процедурами.
Бинарное дерево схематически можно представить следующим образом:
T – выделенная вершина – корень, L – левое поддерево, R – правое поддерево.
Тогда для прямого обхода используется алгоритм TLR. Он включает следующие шаги:
проcмотр корня T
просмотр с помощью алгоритма TLR левого поддерева L
просмотр с помощью алгоритма TLR правого поддерева R
Обход в обратном порядке реализуется с помощью алгоритма LRT:
обход левого поддерева с помощью алгоритма LRT
обход правого поддерева с помощью алгоритма LRT
просмотр корня T
Симметричный обход реализуется с помощью алгоритма LTR:
просмотр левого поддерева с помощью алгоритма LTR
просмотр корня T
просмотр правого поддерева с помощью алгоритма 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, T:TREE); - процедура обхода в прямом порядке вершины поддерева, корнем которого является вершина p дерева T.
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, T:TREE);
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, T:TREE);
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;
В качестве примера алгоритма обхода рассмотрим алгоритм сортировки, использующий бинарное дерево для представления данных. При построении сортирующего дерева очередная запись сравнивается со значением ключа корня. Если ключ этой записи меньше чем ключ корня, то он сравнивается с левым потомком, если больше или равен, то с правым потомком. Такое сравнение производится до тех пор, пока не будет обнаружено отсутствие левого или правого потомка. Тогда эта очередная запись становится потомком. После построения такого дерева для сортировки достаточно обойти его в симметричном порядке.
Пусть входная последовательность данных имеет вид:
14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5
№ вершины |
4 |
2 |
14 |
12 |
15 |
8 |
5 |
9 |
1 |
6 |
3 |
10 |
13 |
7 |
11 |
ключ |
3 |
4 |
4 |
5 |
5 |
7 |
9 |
9 |
14 |
14 |
15 |
16 |
17 |
18 |
20 |