Прохождение бинарных деревьев
В зависимости от последовательности обхода поддеревьев различают три вида обхода (прохождения) деревьев (рис.4.9):
1. Сверху вниз А, В, С.
2. Слева направо или симметричное прохождение В, А, С.
3. Снизу вверх В, С, А.
Наиболее часто применяется второй способ.
Ниже приведены рекурсивные алгоритмы прохождения бинарных деревьев.
| subroutine pretrave (tree) ‘сверху вниз
if tree <> nil then print info(tree) pretrave(left(tree)) pretrave(right(tree)) endif return subroutine intrave (tree) ‘симметричный if tree <> nil then intrave(left(tree)) print info(tree) intrave(right(tree)) endif return | Procedure pretrave (tree: tnode)
Begin if tree <> nil then begin WriteLn(Tree^.Info); Pretrave(Tree^.left); Pretrave(Tree^.right); End; end; procedure intrave (tree: tnode) begin if tree <> nil then begin intrave(Tree^.left); writeLn(Tree^.info); intrave(Tree^.right); end; end; |
Поясним подробнее рекурсию алгоритма обхода дерева слева направо.
Пронумеруем строки алгоритма
intrave (tree):
1 if tree <> nil
2 then intrave (left(tree))
3 print info (tree)
4 intrave (right (tree))
5 endif
6 return
Обозначим указатели: t > tree; l >
left; r > right
На приведенном рис. 4.11 проиллюстрирована последовательность вызова процедуры intrave (tree) по мере обхода узлов простейшего дерева, изображенного на рис. 4. 10.
