Другие обходы дерева. Обход в ширину

Есть задачи, в которых порядок обхода важен. В задаче о вычислении нижние вершины должны быть обработаны раньше, чем верхние.

Л П

К<Л<П Л П К - корень КЛП-обход

Порядок обработки: корень, левая ветка, правая ветка.

ЛПК-обход – задача о вычислении (ПЛК).

Обход КЛП даёт самую простую спецификацию обхода дерева.

1) КЛП – наиболее важный (см. Рекурсия).

2) Обходы “в ширину”, то есть такие порядки, в которых последовательности одинаковой длины соседствуют друг с другом (сгруппированы).

Задача. Найти в дереве вхождение заданного значения от ближайшего корня.

Procedure Поиск_в_ширину (root:pNode;x:tInfo;var found:boolean;var pt:pNode);

var level:{последовательность вершин одного уровня};

Л П

Л П

Begin

found:=false;

put(level,root);

while {не кончились уровни} and not found and level<>0 do

begin

{искать на текущем уровне нужные значения}

{обеспечить доступ на следующий уровень}

while not {кончились вершины уровня} and not found and level<>0 do

begin

get(level,pt);

{достать текущую вершину уровня}

if pt^.info=x then found:=true

else begin

if pt^.left<>nil then put(newlevel,pt^.left);

ifpt^.right<>nil then put(newlevel,pt^.right);

end;

end;

level:=newlevel;

end;

end;

Структура tLevel – последовательность (динамическая) с двумя операциями – get и put и проверка пустоты. В данном случае неважно, стек это или очередь.

Другой вариант того же алгоритма:

uses Queue;

var q:tQueue;

begin

put(q,root);

found:=false;

{q содержит ссылки на все не пройденные вершины списка}

while not empty(q) and not found do

begin

get(q,pt);

if pt^.info=x then found:=true

else begin

if pt^.left<>nil then put(q,pt^.left);

if pt^.right<>nil then put(q,pt^.right);

end;

end;

end;

Это непременно очередь. Потомки текущей вершины должны обрабатываться после всех вершин текущего уровня.

Дата добавления: 2014-01-05