нужно решить задачу, 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
Правда? У меня другая информация... Вот скриншот программы и результатов работы. Смотрим внимательно...
Что я неправильно делаю?
Автор: Гость 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] ??? }