Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Object Pascal: кроссплатформенные технологии > Организация деревьев

Автор: Kaskad 21.3.2005, 22:34

Интересует, как в Паскале реализовать деревья. smile

Автор: Fedor 21.3.2005, 22:51

По-разному можно smile

А какие деревья?
Можно с помощью динамических структур данных например. Да или просто с помощью матрицы.
Тут многое зависит от того, какие у тебя деревья: если двоичные например, то будет намного легче чем если у вершины может быть много потомков.

Автор: Zero 22.3.2005, 00:24

Цитата(Kaskad @ 21.3.2005, 22:34)

Интересует, как в Паскале реализовать деревья.

ИМХО самый лучший способ, это использовать тип запись, реализованый в динамической памяти. Вот пример для бинарного дерева:

Код


Tree = ^cell;
    cell = record
      Name : string; {имя вершины}
      Parent, LP, RP : Tree; {указатели на предков, левых потомко и правых соответственно}
    end;

Это я использовал в своей курсовой работе, по теме "перевод инфиксной записи представленно бинарным деревом, в польскую"

Автор: Fedor 22.3.2005, 07:29

Если дерево не двоичное, т.е. может быть больше чем два потомка, то вместо LP и RP нужно использовать массив:

Код


Tree = ^cell;    
    cell = record    
      Name : string; {имя вершины}    
      Parent: Tree;
      branches:array[1..100] of tree;
    end;

Автор: Pakshin A. S. 22.3.2005, 12:40

А Parent обязателен? Некоторые задачки этого не требуют... smile

Автор: Kaskad 27.3.2005, 14:22

Как задать корень? и как добавлять новые эементы? нужно использовать New( что-то) ? А что именно? И как освобождать память? smile

Автор: Fedor 27.3.2005, 15:48

Вот, набросал быстро. Работает вроде правильно. С вопросами обращайся smile

Код

type
 tree=^cell;
 cell=record
  num:integer;
  key:integer;
  ln,rn:tree;
 end;

function FindNum(P:tree; K:integer):tree;  {Процедура пытается найти вершину с номером K}
var
 P1:tree;
 Q:tree;
begin
  p1:=p;
  if p1^.num=K then begin FindNum:=P1; exit; end;
  if P1^.ln<>nil then
   begin
     Q:=FindNum(P1^.ln,k);
     if Q<>nil then begin FindNum:=Q; exit; end;
   end;
  if P1^.rn<>nil then
   begin
     Q:=FindNum(P1^.rn,k);
     if Q<>nil then begin FindNum:=Q; exit; end;
   end;
  FindNum:=nil;
end;

procedure ClearStructure(P:tree); {Процедура очищает структуру}
begin
 if P^.ln<>nil then ClearStructure(P^.ln);
 if P^.rn<>nil then ClearStructure(P^.rn);
 Dispose(P);
end;

var
 P:tree;
 root:tree;
 f:text;
 from_,to_,key:integer;
begin
 new(root);
 root^.ln:=nil;
 root^.rn:=nil;
 root^.num:=1; {Номер корня изначально равен 1}
 root^.key:=0;

 assign(f,'input.txt'); reset(f);
 {Данные в текстовом фале расположены так: в каждой строке
    Номер_родителя Номер_потомка Вес_потомка}

 while not EOF(f) do
  begin
    readln(f,from_,to_,key);
    P:=findnum(root,from_); {Смотрим, существует ли уже вершина с номером from_}
    if P=nil then {если не существует, то выходим}
     begin
       writeln('Input error');
       readln;
       ClearStructure(root);
       close(f);
       halt;
     end;
    
    {здесь P - уже указатель на вершину с номером from_. Если у нее уже есть один потомок, то используем второй. Если нету, то используем первый}
    if P^.ln=nil then
     begin
       new(P^.ln);
       P:=P^.ln;
     end
    else
     begin
       new(P^.rn);
       P:=P^.rn;
     end;
    P^.ln:=nil;
    P^.rn:=nil;
    P^.num:=to_;
    P^.key:=key;
  end;

 {WORK WITH THE TREE}

 ClearStructure(root);
 close(f);
end.

Автор: Kaskad 27.3.2005, 16:44

У меня бинарные деревья- true|false smile

Я тоже тут состряпал: smile

Код


program derevo;
type
     tree= ^cell;
     cell= record
     zn:boolean;
     R,L: tree;
     end;

var
roof,son:tree;
sdeep,a:integer;

{poisk}
procedure find(e:tree;deep:integer);
begin
    with e^ do
    begin
    if (r=nil)or(l=nil) then if sdeep>deep  then begin sdeep:=deep;son:=e end;
    if (sdeep>=deep)then begin
                                                 find(r,deep+1);
                                                 find(l,deep+1);
                                                 end;
    end;
end;

{dobavlenie}

procedure add;
var son:tree;

begin
sdeep:=100;
son:=nil;
find(roof,1);
with son^ do If r=nil
          then begin new(r); r^.zn:=false; end
          else begin new(l); l^.zn:=true;  end;

end;


{vivod}
procedure print(e:tree;h:integer; deep:integer);
var i:integer;
begin
if e<>nil then begin for i:=0 to h*deep do
                         Write(' '); Writeln(e^.zn);end;
if e<> nil then
with e^ do
 begin
  if (L<> nil)and(deep<4) then print(L,h,deep+1);
  if (R<> nil)and(deep<4) then print(R,h,deep+1);
 end;
end;

{kill :) }
procedure kill(e:tree);
begin
if e<>nil then with e^ do
                      begin
                      if L<>nil then kill(L);
                      If R<>nil then kill(R);
                      If (L=nil)and(r=nil) then dispose(e);
                      end;
end;

{main}
BEGIN
Writeln('go..');
New(roof);

roof^.zn:=false;
for a:=1 to 10 do add;
print (roof,3,1);
kill(roof);
readln;
END.

Добавлено @ 16:47
.

и в 62 строке выдаёт ошибку! "Инвалит поинтер оператор" почему??? smile

Автор: Fedor 27.3.2005, 18:40

Kaskad Ты не обNILяешь потомков вершины при создании таковой.
Т.е. везде после new(smth) ты должен инициализировать потомков ее как nil.
Например:

Код


New(roof);    
roof^.zn:=false;
roof^.l:=nil;
roof^.r:=nil;

Кроме этого момента такое нужно сделать дважды в процедуре Add.

Кроме того, непонятен раздел переменных в процедуре Add. Насколько я понимаю, son должна быть глобальной переменной, так что в процедуре Add эту переменную нужно убрать.

Автор: Kaskad 30.3.2005, 12:11

Fedor Спасибо! smile

Значит дерево я создал. Всё отично работает. Теперь создаю процедуру random_add. То есть, чтоб добавляла листок к дереву случайно. Как это лучше сделать? Приходит на ум, сделать random(1024). Разложить в битовый массив из 10 элементов и спускаться по дереву с поворотами в право-1 и лево-0.

Может как-нибудь легче это дело можно организовать? smile

Автор: Kaskad 30.3.2005, 14:12

И ещё. У меня такое задание:

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

Раз 20 прочитал и ни чего не понял. Всегда будет корень - будет с максимальным количеством вершин. Или я не прав? smile

Автор: Fedor 30.3.2005, 14:33

Цитата(Kaskad @ 30.3.2005, 12:11)

Приходит на ум, сделать random(1024). Разложить в битовый массив из 10 элементов и спускаться по дереву с поворотами в право-1 и лево-0.

МОжно просто спускаться по дереву и постоянно рендомно генерировать либо 0 либо 1.

Цитата(Kaskad @ 30.3.2005, 14:12)

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

На уровне корня (пусть будет нулевой уровень) у тебя только одна вершина: корневая.
На первом уровне у тебя потомки корня - их может быть один либо два либо ноль.
На втором уровне соотв. от нуля до 2^2
И.т.д.

Тебе просто нужно обойти все дерево и считать кол-во вершин на каждом уровне...