Форум «Всё о Паскале»

Людмила

17.03.2005 3:10

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

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

volvo

17.03.2005 3:41

Цитата(Людмила @ 16.03.05 22:10)

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

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

Код

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-х переменных такого типа...

Людмила

17.03.2005 3:53

Цитата(volvo @ 17.03.05 2:41)

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

Код

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

18.03.2005 22:04

Цитата(Людмила @ 16.03.05 22:53)

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

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

Код

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.

Людмила

18.03.2005 22:40

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

Людмила

19.03.2005 22:05

Код

root^.a := nValue;

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

volvo

19.03.2005 22:20

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

Гость

26.05.2006 16:14

Цитата(volvo @ 16.03.2005 23:41)

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

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

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

volvo

26.05.2006 16:34

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

Нажмите для просмотра прикрепленного файла

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

Гость

26.05.2006 16:55

Цитата(volvo @ 26.05.2006 12:34)

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

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

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

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

Гость

26.05.2006 16:57

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

26.05.2006 17:02

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

Гость

26.05.2006 17:07

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

спасибо