Алгоритмы прохождения деревьев в глубину и в ширину.

Date: 2015-10-07; view: 465.

		При прохождении в глубину представленного дерева, список его вершин, записанных в порядке их посещения, будет выглядеть следующим образом: A, B, C, F, G, H, D, E, I, J, K.

Алгоритм прохождения дерева в глубину:

<пустой стек S>;

<пройти корень и включить его в стек S>;

while <стек S не пуст> do

begin {пусть P – узел, находящийся в вершине стека S}

if <не все сыновья узла Р пройдены>

then <пройти старшего сына и включить его в стек S>

else begin

<исключить из вершины стека узел Р>;

if <не все братья вершины Р пройдены>

then <пройти старшего брата и включить его в стек S>

end;

end;

При прохождении представленного дерева в ширину (по уровням), список его вершин, записанных в порядке их посещения, будет выглядеть следующим образом:

A, B, C, D, E, F, G, H, I, J, K.

Алгоритм прохождения дерева в ширину:

<взять две очереди О1 и О2>;

<поместить корень в очередь О1>;

while <О1 или О2 не пуста> do

if <О1 не пуста> then {Р – узел, находящийся в голове очереди О1}

begin

<исключить узел из очереди О1 и пройти его>;

<поместить все узлы, относящиеся к братьям этого узла Р в очередь О2>;

end

else <O1=O2; O2=Æ> и повторяем цикл.