2015-04-08
3972
Рассмотрим алгоритм правосторонней симметричной прошивки бинарного дерева.
1. Строится бинарное дерево. При этом поля ltag и rtag создаваемых узлов дерева остаются неопределенными, а left и right соответственно указывают на левое или правое поддеревья, либо равны nil. На корень построенного дерева указывает root.
2. Создается головной узел, left которого указывает на корень дерева, а right на сам головной узел:
new(HEAD); HEAD^.left:= root; HEAD^.right:= HEAD; Информационное поле и поля тэгов головного узла можно оставить неопределенными.3. Прошивка правых связей. Вводится дополнительный глобальный указатель y (указатель на узел, предшествующий текущему узлу). Указатель на текущий узел p устанавливаем на корень дерева (p:= HEAD^.llink).
Выполняется симметричный обход дерева. При обработке каждого узла проверяется: если p^.right <>nil, то p^.rtag:=true; иначе p^.rtag:=false; y:=p; (указатель на предшественника). В любом случае выполняем.
Программный код процедур симметричного обхода sim_print и прошивки правых связей rightsew будет выглядеть так:
|
|
|
procedure sim_print(var x:pt);
procedure rightsew(var p:pt);
begin
if y <> nil then
begin
if y^.right=nil then
begin
y^.rtag:= false;
y^.right:= p;
end
else y^.rtag:= true;
end;
y:=p;
end;
begin
if x<> nil then
begin
sim_print(x^.left);
rightsew(x);
sim_print(x^.right);
end;
end;
Рассмотрим алгоритм обхода прошитого бинарного дерева. Пусть HEAD – указатель на головной узел прошитого дерева, p – указатель на текущий узел. Тогда алгоритм симметричного обхода прошитого дерева можно сформулировать следующим образом:
1. Переход к корню дерева (p:= HEAD^.left).
2. До тех пор, пока p^.left<>nil, повторять: p:= p^.left, то есть идти по левой ветви до самого левого узла.
3. Обработка узла p, например, печать p^.info.
4. Если p^.rtag равен false, то p:= p^.right и переход к шагу 3 (к преемнику). Иначе p:= p^.right и переход к шагу 2.
Алгоритм заканчивает работу, когда p станет равным HEAD.
Лабораторная работа №6
Цель работы: научиться прошивать различными способами, а затем обходить бинарные деревья, а также выполнять на них операции с данными.
