Структуры данных. Деревья - 10 стр.

UptoLike

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

Рубрика:

Способы прохождения деревьев определяются рекурсивно. Если дерево

пусто, то никаких действий не выполняется, в противном случае обход выполня-

ется в три этапа

Префиксный обход Инфиксный обход

Обработать узел Пройти левое поддерево

Пройти левое поддерево Обработать узел

Пройти правое поддерево Пройти правое поддерево

Постфиксный обход

Пройти левое поддерево

Пройти правое поддерево

Обработать узел

Обход слева направо (инфиксный обход) часто используется при сорти-

ровке (см. раздел 4 ). Префиксный и постфиксный способы обхода дерева играют

важную роль при анализе текстов на языках программирования.

Все три метода легко представляются как рекурсивные процедуры.

Пример 3.1. Префиксный обход дерева :

procedure PreOrder(T : Tree);

begin

if T <> nil then

begin

{ операция обработки узла дерева , например, writeln( T^.inf );}

PreOrder (T^.L);

PreOrder (T^.R)

end

end; { PreOrder }