Обходы двоичных деревьев

Далее будет рассмотрена операция прямого обхода двоичного дерева в рекурсивной и нерекурсивной форме. Реализации обратного и симметричного обхода аналогична.

procedure PreOrder_BinTree(Node: PTree);

{Рекурсивный обход двоичного дерева в прямом порядке}

begin

writeln(Node^.Data);

if Node^.Left <> nil then PreOrder_BinTree(Node^.Left);

if Node^.Right <> nil then PreOrder_BinTree(Node^.Right);

end;

Листинг 3.22 – Обход двоичного дерева в прямом порядке на языке Pascal

В процедуре, реализующей нерекурсивный обход двоичного дерева, используется стек, хранящий путь от корня дерева до предка текущей вершины. Элементы стека хранят указатели на вершины дерева.

Процедура работает в двух режимах. В первом режиме осуществляется обход по направлению к левым потомкам до тех пор, пока не встретится лист, при этом выполняется печать значений вершин, и занесение указателей на них в стек. Во втором режиме осуществляется возврат по пройденному пути с поочередным извлечением указателей из стека до тех пор, пока не встретится вершина, имеющая еще ненапечатанного правого потомка. Тогда процедура переходит в первый режим и исследует новый путь, начиная с этого потомка.

procedure NR_PreOrder_BinTree(Tree: PTree);

{Нерекурсивный обход двоичного дерева в прямом порядке}

var

Node: Ptree; {Указатель на текущую вершину}

S: ^TypeElement; {Стек указателей вершин}

begin

{Инициализация}

ClearStack(S);

Node := Tree;

while true do

if Node <> nil then begin

writeln(Node^.Data);

PushStack(Node, S);

{Исследование левого потомка вершины Node}

Node := Node^.Left;

end else begin

{Завершена исследование пути, содержащегося в стеке}

if EmptyStack(S) then return;

{Исследование правого потомка вершины Node}

PopStack(Node, S);

Node := Node^.Right;

end;

end;

Листинг 3.23 – Нерекурсивный обход двоичного дерева в прямом порядке