Материал: АиСД деревья
Еще один полезный способ обхода бинарного дерева обход в горизонтальном порядке (в ширину). При таком способе узлы бинарного дерева проходятся слева направо, уровень за уровнем от корня вниз (поколение за поколением от старших к младшим). Легко указать нерекурсивную процедуру горизонтального обхода, аналогичную процедуре КЛП-обхода (в глубину), но использующую очередь вместо стека:
-
procedure обход_горизонтальный (b: BTree);
var Q: queue of BTree;
p: BTree;
begin
Q := Create;
Q b;
while not Null (Q) do
begin
p Q;
посетить (p);
if not Null (Left (p)) then Q Left (p);
if not Null (Right (p)) then Q Right (p)
end{while}
end{обход_горизонтальный}
Здесь каждый узел дерева рассматривается как корень соответствующего поддерева, и этому поддереву сопоставляется запись из трех полей: поле Info хранит значение корня (типа Elem), а поля LSub и RSub указатели на левое и правое поддеревья. Пустому дереву сопоставляется константа NilBT (на абстрактном уровне обозначаемая ранее как ). На рис. 3.9, а, б изображены бинарное дерево и его представление в ссылочной реализации.
Интерфейсная часть модуля для работы с бинарным деревом на основе ссылочной реализации представлена на рис. 3.10.
Здесь в сравнении с функциональной спецификацией из 3.2 добавлены функция CreateBT и процедура DestroyBT, используемые для начала и завершения работы с экземпляром динамической структуры. Функция CreateBT формально специфицируется соотношениями
CreateBT: BT; Null (CreateBT) = true.
Error: Reference source not found
Рис. 3.9. Пример бинарного дерева (a) и его ссылочного представления (б)
Кроме того, добавлена процедура Otkaz, вызываемая при попытке некорректного применения основных функций.
Тип узлов дерева Elem должен быть задан в модуле GlobalBT, например, таким образом:
-
Unit GlobalBT;
Interface type Elem = Char;
Implementation
begin
end.
-
{Модуль для работы с бинарными деревьями}
Unit BinTree;
Interface
uses GlobalBT;
const
NilBT = nil;
type
BinT = ^Node; {представление бинарного дерева}
{тип Elem описан в GlobalBT}
Node = record {узел:
Info: Elem; { содержимое}
LSub: BinT; { левое поддерево}
RSub: BinT { правое поддерево}
end {Node};
function CreateBT: BinT;
function NullBT (t: BinT): Boolean;
function RootBT (t: BinT): Elem;
function LeftBT (t: BinT): BinT;
function RightBT (t: BinT): BinT;
function ConsBT (e: Elem; LS, RS: BinT): BinT;
procedure DestroyBT (var b: BinT);
procedure Otkaz (n: Byte);
{‑‑---------------------------------------------------------------------------------}
Implementation
...
end.
Рис. 3.10. Модуль для работы с бинарными деревьями
Часть Implementation модуля BinTree может иметь следующий вид:
Implementation
procedure Otkaz (n: Byte);
begin
Case n of
1: Write ('ОТКАЗ: RootBT (Null_Bin_Tree)!');
2: Write ('ОТКАЗ: LeftBT (Null_Bin_Tree)!');
3: Write ('ОТКАЗ: RightBT (Null_Bin_Tree)!');
4: Write ('ОТКАЗ: исчерпана память!')
else Write ('ОТКАЗ: ?')
end;
Halt
end {Otkaz};
function CreateBT: BinT;
begin
CreateBT := nil
end {CreateBT};
function NullBT (t: BinT): Boolean;
begin
NullBT := (t = nil)
end {NullBT};
function RootBT (t: BinT): Elem;
begin
if t <> nil then RootBT := t^.Info else Otkaz(1)
end {RootBT};
function LeftBT (t: BinT): BinT;
begin
if t <> nil then LeftBT := t^.LSub else Otkaz(2)
end {LeftBT};
function RightBT (t: BinT): BinT;
begin
if t <> nil then RightBT := t^.RSub else Otkaz(3)
end {RightBT};
function ConsBT (e: Elem; LS, RS: BinT): BinT;
var b: BinT;
begin
if MaxAvail >= SizeOf (Node) then
begin
New (b);
b^.Info:= e;
b^.LSub:= LS;
b^.RSub:= RS;
ConsBT:= b
end
else
Otkaz(4)
end {ConsBT};
procedure DestroyBT(var b: BinT);
begin
if b <> nil then
begin
DestroyBt (b^.LSub);
DestroyBt (b^.RSub);
Dispose (b)
end
end {DestroyBT};
begin
end.
Далее приведем пример использования модуля BinTree, в котором для ввода бинарного дерева из файла и вывода его на экран используется КЛП-обход бинарного дерева, описанный в 3.4.
{Пример работы с бинарными деревьями}
Uses BinTree;
var b: BinT;
Fin: Text;
function EnterBt: BinT;
{ввод узлов в КЛП-порядке и построение бинарного дерева}
var c: Char;
begin
Read (Fin, c);
if c = '/'
then EnterBT:= NilBT {Create}
else EnterBT:= ConsBT (c, EnterBT, EnterBT)
end {EnterBT};
procedure OutBT(b: BinT);
{вывод узлов бинарного дерева в КЛП-порядке}
begin
if not NullBT (b) then
begin
Write (RootBT (b));
OutBT (LeftBT (b));
OutBT (RightBT (b))
end
else Write ('/')
end {OutBT};
procedure DisplayBT (b: BinT);
{построчный вывод повернутого изображения бинарного дерева}
begin
if NullBt (b) then {?}
else
begin
Write (RootBT (b));
if not NullBT (RightBT (b)) then
begin
Write (' '); {вправо}
DisplayBT (RightBT (b));
Write (#8); Write (#8); {возврат влево}
end;
if not NullBT (LeftBT (b)) then
begin
Write (#10); {вниз}
Write (' '); {вправо}
DisplayBT (LeftBT (b));
Write (#8); Write (#8); {возврат влево}
end;
end {else}
end {DisplayBT};
begin
Assign (Fin, 'inbintree.dat'); Reset (Fin);
b := EnterBT;
WriteLn ('Построили бинарное дерево по его КЛП-представлению,',
'вот КЛП-представление :');
OutBT (b); WriteLn;
WriteLn ('... а теперь вид дерева ...');
DisplayBT (b);
WriteLn;
DestroyBt (b);
end.
Отметим, что в процедуре DisplayBT использованы особенности оператора Write языка Турбо-Паскаль: перемещение «каретки» на предыдущую позицию в строке Write (#8) и на ту же позицию, но на следующей строке Write (#10). Более универсальная процедура DisplayBT1, не использующая эти особенности языка Турбо-Паскаль, имеет следующий вид:
procedure DisplayBT1 (b: BinT; n: integer);
{построчный вывод повернутого изображения бинарного дерева без возврата каретки}
{n уровень узла}
var i: integer;
begin
if NullBT (b) then {Writeln}
else
begin
Write (' ', RootBT (b));
if NullBT (RightBT (b))
then Writeln {вниз}