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

[Людмила]

нужно решить задачу, 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!!!
Сейчас попробую.