Помощь - Поиск - Пользователи - Календарь
Полная версия: Программа сравнения двух бинарных деревьев
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
zabludshiy
Помогите, пожалуйста, разобраться в следующей программе.

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 (я так понял, что выход осуществляется когда тор станет меньше нуля, но по тексту он только возрастает, так каким образом осуществляется выход из цикла?).
Буду БЛАГОДАРЕН Всем, кто может помочь разобраться с этой ЗАДАЧЕЙ.
zabludshiy
Тема закрыта
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.