Процедуры "обхода" дерева
Пусть задано бинарное дерево :
Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева :
1) Обход сверху вниз (корень посещается ранее, чем поддеревья) : A, B, C ;
2) Слева направо : B, A, C ;
3) Снизу вверх (корень посещается после поддеревьев) : B, C, A .
Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.
Рекурсивные процедуры обхода дерева :
1) PROCEDURE pretrave (tree)
IF tree<>nil
THEN PRINT info (tree)
pretrave (left (tree))
pretrave (right (tree))
END IF
RETURN
2) PROCEDURE intrave (tree)
IF tree<>nil
THEN intrave (left (tree))
PRINT info (tree)
intrave (right (tree))
END IF
RETURN
3) PROCEDURE postrave (tree)
IF tree<>nil
THEN postrave (left (tree))
postrave (right (tree))
PRINT info (tree)
END IF
RETURN
