двоичное дерево, создание, вставка, печать, поиск, удален Опции

[andr]

мне надо сделать задачку с двочным деревом. выкладываю то, что сделал на данный момент, НЕ РАБОТАЮТ процедуры поиска и удаления. причина - не знаю. поиск выдает неправильный ответ, удаление даже не компилируется.

может быть кто-нибудь ошибку найдет?

Код

uses crt;

type u=^bintree;
    rec = record
      dist : string;
      num : string;
      name : string;
      date : string;
    end;
    bintree = record
      inf : rec;
      l, r : u;
    end;

var
 tree : u;
 fi, fo : text;

procedure ins(var tr : u; p : bintree); {работает}
begin
 if tr = nil then
 begin
   new(tr);
   tr^ := p;
 end
 else if p.inf.name < tr^.inf.name then
 ins(tr^.l,p) else
 ins(tr^.r,p);
end;

procedure insall; {работает}
var z : bintree;
begin
 while not seekeof(fi) do
 begin
   with z do begin
     readln (fi, inf.dist, inf.num, inf.name, inf.date);
     l := nil;
     r := nil;
     ins(tree, z);
   end;
 end;
end;

procedure printtree(t : u); {работает}
begin
 if t <> nil then
 begin
   printtree(t^.l);
   with t^.inf do
   begin
     writeln(fo, date, num, dist, name);
   end;
   printtree(t^.r);
 end;
end;

procedure findname(tree : u; x : string); {компилируется, но выдает неправ. ответ}
begin
 while tree <> nil do
 begin
   if x = tree^.inf.name then
   with tree^.inf do
   begin
     writeln(fo, date, num, dist, name);
   end else if x < tree^.inf.name then tree := tree^.l
                                  else tree := tree^.r;
 end;
 writeln(fo, 'not found')
end;

procedure delall(tree : u); {не компилируется}
begin
 if tree <> nil then
 begin
   delall(tree^.r);
   delall(tree^.r);
   dispose(tree);
   tree := nil;
 end;
end;

begin
 assign(fo, 'out.txt');
 rewrite(fo);
 assign(fi, 'in.txt');
 reset(fi);
 tree := nil;
 insall;
 printtree(tree);
 close(fo);
 close(fi);
end.

Сообщение отредактировано: andr - 31.10.2004 23:41

[volvo]

andr

Чем пробовали компилировать? У меня в ТР 7 все откомпилировалось на ура... Хотя

Код

procedure delall(tree : u);
begin
if tree <> nil then
begin
  delall(tree^.r);
  delall(tree^.r);
  dispose(tree);
  tree := nil;
end;
end;

я бы заменил на

Код

procedure delall(tree : u);
begin
if tree <> nil then
begin
  delall(tree^.r);
  delall(tree^.l); { Внимательно! }
  dispose(tree);
  tree := nil;
end;
end;

;)

Код

procedure findname(tree : u; x : string);
begin
while tree <> nil do
begin
  if x = tree^.inf.name then
  with tree^.inf do
  begin
    writeln(fo, date, num, dist, name);
    { !!!! Выходим !!!!! }
    Exit;
  end else if x < tree^.inf.name then tree := tree^.l
                                 else tree := tree^.r;
end;
writeln(fo, 'not found')
end;

Сообщение отредактировано: volvo - 1.11.2004 0:36

[andr]

volvo, спасибо, я сам заметил, решил написать. но он в выходной файл пишет какие-то остатки от дерева, те заменяет некоторые символы. этого явно не должно быть. или у меня компилятор левый какой-то ???

p.s. как с поиском дела?

Сообщение отредактировано: andr - 1.11.2004 0:39

[andr]

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

Код

procedure findname(tr : u; x : string);
begin
 while tr <> nil do
 begin
   if x = tr^.inf.name then
   begin
   with tr^.inf do
   begin
     writeln(fo, date, num, dist, name);
   end;
   exit;
   end else if x < tr^.inf.name then tr := tr^.l
                                  else tr := tr^.r;
 end;
 writeln(fo, 'not found')
end;

все равно пишет not found в любом случае.

Сообщение отредактировано: andr - 1.11.2004 0:54

[Digitalator]

А не лучше ли delall без рекурсии делать воизбежание многих могущих возникнуть неприятностей? <_<

Сообщение отредактировано: Digitalator - 1.11.2004 21:25

[Altair]

Хм... если рекрсия хорошо реализованна, то не должно возникнуть проблемм.
Рекурсия хорошая вещь при правильной реализации.

[APAL]

Ссылка действительно интересная.
Только читать ее будут единицы... даже если вырезать только самое важное.

[andr]

я понял, в чем была проблема:

Код

readln (fi, inf.dist, inf.num, inf.name, inf.date);

т.к. все данные типа string, в dist записывалась вся строка, а остальные поля оставались пустыми. с integer такой вариант ввода заработал бы. на днях выложу все сделанное до конца. процедуры должны быть правильными.

Сообщение отредактировано: andr - 2.11.2004 15:17

[Доча]

... удалено...


Пожалуйста, если вы хотите задать вопрос, то создайте новый топик, а не пишите его в чужой. Второй раз удаляю...

Сообщение отредактировано: APAL - 2.11.2004 21:27

[Digitalator]

Хм... если рекрсия хорошо реализованна, то не должно возникнуть проблемм.
Рекурсия хорошая вещь при правильной реализации.

и чем же она хороша?

PS:
Спросите об этом мальчишку,
Что в доме напротив живет -
Он с рекурсией этой ложиться,
С рекурсией же он встает...
:D :D :D

[Altair]

Рекурсия красива ... она доставляет огромное эстетическое наслаждение

и чем же она хороша?

Ответил?

А вот в Прологе например, это незаменимый инструмент!

[andr]

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