IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> деревья, помогите решить задачу
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Женский

Репутация: -  1  +


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

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


--------------------
хороших людей мало... полезных ещё меньше....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата(Людмила @ 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-х переменных такого типа...
smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Женский

Репутация: -  1  +


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



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


--------------------
хороших людей мало... полезных ещё меньше....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата(Людмила @ 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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Женский

Репутация: -  1  +


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


--------------------
хороших людей мало... полезных ещё меньше....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Женский

Репутация: -  1  +


Код

         root^.a := nValue;
     


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


--------------------
хороших людей мало... полезных ещё меньше....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Проверяйте, я исправил... (кстати это должен был быть не "Type mismatch", а "Field identifier expected" )...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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


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

плучается equal присваевается значении истины т.е. типо деревья ровны...
помогите разобрать?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






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

Прикрепленное изображение

Что я неправильно делаю? rolleyes.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата(volvo @ 26.05.2006 12:34)
Правда? У меня другая информация... Вот скриншот программы и результатов работы.
Смотрим внимательно...


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

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

делается неверное заключение, что два дерева равны. Эти два дерева не могут быть равны, так как в узлах записаны совершенно разные значения.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






For i := 1 To Length(s1) Do
root1 := AddToTree(root1, s[i]); { <--- Может, все-таки, s1[i] ??? }
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






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

спасибо
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 15:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name