деревья, помогите решить задачу Опции

[Людмила]

нужно решить задачу, FAQ уже читала, пыталась сделать сама, ну просто ни чего не получается...

Разработать программу, которая определяет, равны ли два бинарных дерева.

[volvo]

Разработать программу, которая определяет, равны ли два бинарных дерева.

Значит, так...
Алгоритм сравнения рекурсивный: два дерева равны, если корень одного дерева содержит такое же значение, что и корень второго дерева, и при этом равны соответствующие поддеревья. Пустые деревья равны по определению.

Код

function equal(p1, p2 : pptr) : boolean;
 begin
   if (p1=nil) and (p2=nil) then equal := true
   else if (p1<>nil) and (p2<>nil)
            then equal := (p1^.info= p2^.info) and equal(p1^.llink, p2^.llink)
                                 and equal(p1^.rlink, p2^.rlink)
            else equal := false
end;

где тип ptr - указатель на узел дерева...
Если поле info содержит НЕ встроенный, а определенный пользователем тип данных, может понадобиться написание дополнительной функции сравнения 2-х переменных такого типа...

[Людмила]

Значит, так...
Алгоритм сравнения рекурсивный: два дерева равны, если корень одного дерева содержит такое же значение, что и корень второго дерева, и при этом равны соответствующие поддеревья. Пустые деревья равны по определению.

Код

function equal(p1, p2 : pptr) : boolean;
 begin
   if (p1=nil) and (p2=nil) then equal := true
   else if (p1<>nil) and (p2<>nil)
            then equal := (p1^.info= p2^.info) and equal(p1^.llink, p2^.llink)
                                 and equal(p1^.rlink, p2^.rlink)
            else equal := false
end;

где тип ptr - указатель на узел дерева...
Если поле info содержит НЕ встроенный, а определенный пользователем тип данных, может понадобиться написание дополнительной функции сравнения 2-х переменных такого типа...

Спасибо огромное!!!! а как формировать эти деревья? как я поняла задание дерева происходит линейно, т.е. в строку, потом из этой строки и формируется дерево?

[volvo]

а как формировать эти деревья? как я поняла задание дерева происходит линейно, т.е. в строку, потом из этой строки и формируется дерево?

Ну, можно и так:

Код

Type
 pptr = ^TTree;
 TTree =
   Record
     info: Char;
     llink, rlink: pptr;
   End;

{ Добавляем значение в дерево }
Function AddToTree(root: pptr;
        nValue: Char): pptr;
 Begin
   (* If no child - create new item *)
   If root = nil Then
     Begin
       root := New(pptr);
       root^.info := nValue;
       root^.llink := nil;
       root^.rlink := nil;
       AddToTree := root; Exit
     End;

   If root^.info < nValue Then
     root^.rlink := AddToTree(root^.rlink, nValue)
   Else
     root^.llink := AddToTree(root^.llink, nValue);
   AddToTree := root
 End;

Var
 s: String;
 root: pptr;
 i: byte;
Begin
 s := 'This is a test';
 root := nil;
 For i := 1 To Length(s) Do
   root := AddToTree(root, s[i]);
 { Теперь в двоичном дереве поиска, на которое
    указывает root, хранится строка s }
End.

[Людмила]

Спасибо, volvo!!!
Сейчас попробую.

[Людмила]

Код

         root^.a := nValue;
     

в этой строчке выдаёт ошибку "type mismatch"

[volvo]

Проверяйте, я исправил... (кстати это должен был быть не "Type mismatch", а "Field identifier expected" )...

[Гость]

Значит, так...
Алгоритм сравнения рекурсивный: два дерева равны, если корень одного дерева содержит такое же значение, что и корень второго дерева, и при этом равны соответствующие поддеревья. Пустые деревья равны по определению.

Мне нужна подобная функция попробыла использовать вашу но она не рабоет если ввеодишь например древья:
123654
25841

плучается equal присваевается значении истины т.е. типо деревья ровны...
помогите разобрать?

[volvo]

Правда? У меня другая информация... Вот скриншот программы и результатов работы.
Смотрим внимательно...



Что я неправильно делаю?

[Гость]

Правда? У меня другая информация... Вот скриншот программы и результатов работы.
Смотрим внимательно...

Сори! он показывает что два дерава ровны когда в них оденаовое количство симвалов.
например:
12598
fghjf

получаются ровны

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

[Гость]

uses Crt;
Type
 pptr = ^TTree;
 TTree =
   Record
     info: Char;
     llink, rlink: pptr;
   End;

Function AddToTree(root: pptr;
        nValue: Char): pptr;
 Begin
     If root = nil Then
     Begin
       root := New(pptr);
       root^.info := nValue;
       root^.llink := nil;
       root^.rlink := nil;
       AddToTree := root; Exit
     End;

   If root^.info < nValue Then
     root^.rlink := AddToTree(root^.rlink, nValue)
   Else
     root^.llink := AddToTree(root^.llink, nValue);
   AddToTree := root
 End;

function equal(p1, p2 : pptr) : boolean;
 begin
   if (p1=nil) and (p2=nil) then equal := true
   else if (p1<>nil) and (p2<>nil)
            then equal := (p1^.info= p2^.info) and equal(p1^.llink, p2^.llink)
                                 and equal(p1^.rlink, p2^.rlink)
            else equal := false
end;

Var
 s, s1: String;
 root, root1: pptr;
 i: byte;
Begin
  ClrScr;
  begin
   writeln('vvedite simvoly pervogo dereva:');
   readln(s);
   root := nil;
   For i := 1 To Length(s) Do
   root := AddToTree(root, s[i]);
  end;
  begin
   writeln('vvedite simvoly vtorogo dereva:');
   read(s1);
   root1 := nil;
   For i := 1 To Length(s1) Do
   root1 := AddToTree(root1, s[i]);
   end;

   if equal(root, root1)=true then  writeln('dwa dereva ravny')
   else  writeln('dwa dereva ne ravny');
   Readkey
End.

[volvo]

For i := 1 To Length(s1) Do
  root1 := AddToTree(root1, s[i]); { <--- Может, все-таки, s1[i] ??? }

[Гость]

ух ты... работает

спасибо