Правила форума
Прочтите прежде чем задавать вопрос!
program Laba2;
{Программа сравнения двух бинарных деревьев.
ВНИМАНИЕ: входные данные считаются заведомо корректными,
никакая проверка ошибок не предусмотрена!}
const
TAB = chr(9); {символ табуляции}
type
Element = Integer;
Tree = ^Node; {дерево}
Node = record {вершина дерева}
Data: Element; {данные}
Left: Tree; {левый сын}
Right: Tree; {правый сын}
end;
var
inFile1, inFile2: Text; {файлы двух деревьев}
inTree1, inTree2: Tree; {сцепленные представления двух деревьев}
procedure ReadTree(var F: Text; var T: Tree);
{Читает дерево, представленное иерархическим текстом, из файла F
и строит сцепленное представление дерева T}
var
level: Integer;
currLine: String;
currNumber: String;
dataStr: String;
currPos: Integer;
code: Integer;
function GetWord: String;
{Выделяет из CurrLine очередную последовательность символов,
отличных от пробела и табуляции}
var
result: String;
begin
while (currPos <= Length(currLine)) and ((currLine[currPos] = ' ')
or (currLine[currPos] = TAB)) do
currPos := currPos + 1;
result := '';
while (currPos <= Length(currLine)) and (currLine[currPos] <> ' ')
and (currLine[currPos] <> TAB) do begin
result := result + currLine[currPos];
currPos := currPos + 1;
end;
GetWord := result;
end; {GetWord}
procedure RecurseRT(var T: Tree; level: Integer);
{Читает непустое поддерево T из файла.
Параметр level содержит длину номера корневой вершины поддерева.
В момент вызова этот номер уже считан из текущей введенной строки.
В момент возврата считан номер вершины, не принадлежащей введенному
поддереву}
begin
T := New(Tree);
T^.Left := nil;
T^.Right := nil;
dataStr := GetWord; {данные корневой вершины}
Val(dataStr, T^.Data, Code);
Readln(F, currLine);
currPos := 1;
currNumber := GetWord;
while Length(currNumber) > level do begin {это сыновья}
if currNumber[Length(currNumber)] = '0' then
RecurseRT(T^.Left, level + 1)
else
RecurseRT(T^.Right, level + 1);
end;
end; {RecurseRT}
begin {ReadTree}
if EOF(F) then {пустое дерево}
T := nil
else begin
Readln(F, currLine);
currPos := 1;
currNumber := GetWord;
RecurseRT(T, 1);
end;
end; {ReadTree}
procedure PrintTree(Header: String; var T: Tree);
{Выдает на стандартный вывод текстовое представление дерева T,
предваряя его заголовком Header}
procedure RecursePT(T: Tree; number: String);
{Выдает на стандартный вывод текстовое представление поддерева T.
Параметр number задает номер корневой вершины}
var
i: Integer;
begin {RecursePT}
if T = nil then
Exit;
{Сначала печать корня}
for i := 1 to Length(number) do {Отступ}
Write(' ');
Write(number + ' ');
Writeln(T^.Data);
{Теперь сыновья}
RecursePT(T^.Left, number + '0');
RecursePT(T^.Right, number + '1');
end; {RecursePT}
begin {PrintTree}
Writeln;
Writeln(Header);
RecursePT(T, '0');
end; {PrintTree}
function TreeEquRec(T1, T2: Tree): Boolean;
{Проверяет равенство двух деревьев T1 и T2.
Рекурсивный вариант}
begin
if T1 = nil then
if T2 = nil then
TreeEquRec := true
else
TreeEquRec := false
else
if T2 = nil then
TreeEquRec := false
else
if T1^.Data <> T2^.Data then
TreeEquRec := false
else
TreeEquRec := TreeEquRec(T1^.Left, T2^.Left)
and TreeEquRec(T1^.Right, T2^.Right);
end; {TreeEquRec}
function TreeEquNonRec(T1, T2: Tree): Boolean;
{Проверяет равенство двух деревьев T1 и T2.
Нерекурсивный вариант}
var
Stack: array[1..100, 1..2] of Tree; {Стек для двух деревьев}
Top: Integer; {Указатель вершины стека}
begin
Top := 1;
Stack[Top, 1] := T1;
Stack[Top, 2] := T2;
while Top > 0 do begin {пока в стеке есть нерассмотренные поддеревья}
T1 := Stack[Top, 1];
T2 := Stack[Top, 2];
Top := Top - 1;
if T1 = nil then
if T2 = nil then begin
{В отличие от рекурсивного варианта, здесь еще рано принимать
решение, потому что Exit будет означать завершение всей работы,
без рассмотрения оставшихся поддеревьев!}
{TreeEquNonRec := true;
Exit;}
end
else begin
TreeEquNonRec := false;
{Если хоть одно различие есть, то деревья различны}
Exit;
end
else begin
if T2 = nil then begin
TreeEquNonRec := false;
Exit;
end
else begin
if T1^.Data <> T2^.Data then begin
TreeEquNonRec := false;
Exit;
end
else begin
{Раз не удалось найти различий в корневой вершине,
продолжим на поддеревьях}
Stack[Top+1, 1] := T1^.Left;
Stack[Top+1, 2] := T2^.Left;
Stack[Top+2, 1] := T1^.Right;
Stack[Top+2, 2] := T2^.Right;
Top := Top+2;
end;
end;
end;
end;
{Поддеревья кончились.
Поскольку различий найти не удалось, деревья равны}
TreeEquNonRec := true;
end; {TreeEquNonRec}
begin {Laba2}
Assign(inFile1, 'Tree1.txt');
Reset(inFile1);
ReadTree(inFile1, inTree1);
PrintTree('Первое дерево:', inTree1);
Assign(inFile2, 'Tree2.txt');
Reset(inFile2);
ReadTree(inFile2, inTree2);
PrintTree('Второе дерево:', inTree2);
Writeln;
if TreeEquRec(inTree1, inTree2) then
Writeln(' Рекурсивное решение: деревья равны')
else
Writeln(' Рекурсивное решение: деревья различны');
if TreeEquNonRec(inTree1, inTree2) then
Writeln('Нерекурсивное решение: деревья равны')
else
Writeln('Нерекурсивное решение: деревья различны');
end.
Сам никак не могу понять какую структуру должны иметь файлы tree1.txt и tree2.txt. Как работает процедура ReadTree тоже не получается разобраться вот уже 3 неделю. Также не разобрался с процедурой TreeEquNonRec в части выхода из цикла при Top>0 (я так понял, что выход осуществляется когда тор станет меньше нуля, но по тексту он только возрастает, так каким образом осуществляется выход из цикла?).
Буду БЛАГОДАРЕН Всем, кто может помочь разобраться с этой ЗАДАЧЕЙ.
