Версия для печати темы

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

Форум «Всё о Паскале» _ Задачи _ Деревья, поиск по ключу

Автор: lena4k@ 8.12.2006 1:40

smile.gifЗдрасьте smile.gif Я у вас тут впервые, очень надеюсь wub.gif
Вот моя задачка: определяет число вхождений ключа x в дерево t.
Задачка вроде несложная, только вот в этих "деревьях" я как-то блукаю. mega_chok.gif
Вот что я сделала:

USES CRT;
type
  TKey = integer;
  PNode = ^TNode;
  TNode = record
          key : TKey;
          left,right : PNode;
          end;
{-------------------------------------------------------------------}
PROCEDURE make(var p : PNode; x : Tkey);
begin
  new(p);
  p^.key:=x;
  p^.left:=nil;
  p^.right:=nil;
end;


PROCEDURE insert(var p : PNode; h : integer);
begin
  make(p^.left,Random(10){h});
  make(p^.right,Random(10){h});
  if h > 1 then
  begin
  insert(p^.left,h-1);
  insert(p^.right,h-1);
  end;
end;
{--------------------------------------------------------}
PROCEDURE inorder(var p : PNode);

begin
  if p<>nil then
  begin
  inorder(p^.left);
  Write(p^.key,'  '); 
  inorder(p^.right);
  end;
end;
{-----------------------------------------------------}
PROCEDURE poisk(var p : PNode);
var k : integer; flag : boolean; x : Tkey; tree : PNode;
begin
{******** poisk klutha *******************}
p:=tree;
While (p <> nil) and (p^.key <> x) do
  if p < p^.key then begin
  p:=p^.left
  else p:=p^.right;
  end;
end;
flag:=(p <> nil);
{******************************************}
  k:=0;
  if p^.key = x then
  begin
  k:=k+1;
  end;
end;

{--------------------------------------------------------}
var p : PNode; x : Tkey;
h,k : integer; tree : PNode;
begin
clrscr;
h:=2;
tree:=nil;
make(tree,Random(10){0});
insert(tree,h);
Writeln('obratnij obhod dereva: ');
inorder(tree);

Writeln;
Writeln;
Writeln('vvedite kluth x: ');
Readln(x);

poisk(tree);

Writeln;
Write('thislo vhogdenij klutha x: ',k);

readln;
end.


Но я наверное что-то не так поняла. Помогите blink.gif !!!
Прикрепленный файл  DER.PAS ( 1.55 килобайт ) Кол-во скачиваний: 437

Автор: volvo 8.12.2006 2:14

Так лучше? smile.gif 

USES CRT;
type
  TKey = integer;
  PNode = ^TNode;
  TNode = record
          key : TKey;
          left,right : PNode;
          end;
{-------------------------------------------------------------------}
PROCEDURE make(var p : PNode; x : Tkey);
begin
  new(p);
  p^.key:=x;
  p^.left:=nil;
  p^.right:=nil;
end;


PROCEDURE insert(var p : PNode; h : integer);
begin
  make(p^.left,Random(10){h});
  make(p^.right,Random(10){h});
  if h > 1 then
  begin
  insert(p^.left,h-1);
  insert(p^.right,h-1);
  end;
end;
{--------------------------------------------------------}
PROCEDURE inorder(var p : PNode);

begin
  if p<>nil then
  begin
  inorder(p^.left);
  Write(p^.key,'  ');
  inorder(p^.right);
  end;
end;
{-----------------------------------------------------}

function poisk(p: PNode; X: TKey): integer;
var value: integer;
begin

  value := 0;
  if p = nil then poisk := 0
  else begin

    if X = p^.key then value := 1;
    poisk := value + poisk(p^.Left, X) + poisk(p^.Right, X);

  end;

End;

{--------------------------------------------------------}
var p : PNode; x : Tkey;
h,k : integer; tree : PNode;
begin
clrscr;
h:=2;
tree:=nil;
make(tree,Random(10){0});
insert(tree,h);
Writeln('obratnij obhod dereva: ');
inorder(tree);

Writeln;
Writeln;
Writeln('vvedite kluth x: ');
Readln(x);

k := poisk(tree, x);

Writeln;
Write('thislo vhogdenij klutha x: ',k);

readln;
end.


P.S. В следующий раз давай топику более осмысленное название...

Автор: lena4k@ 9.12.2006 4:10

Спасибо большущее VOLVO :give_ro Первый раз решилась вот так по интернету попросить помочь мне и сомневалась, если честно, что кто-то станет помогать! МИР НЕ БЕЗ ДОБРЫХ ЛЮДЕЙ!!!
Очень интересное решение с помощью функции good.gif !!!

А вот ещё решение этой задачи (с процедурой):

USES CRT;
type
TKey = integer;
PNode = ^TNode;
TNode = record
key : TKey;
left,right : PNode;
end;
{-----------------------------------}
PROCEDURE make(var p : PNode; x : Tkey);
begin
new(p);
p^.key:=x;
p^.left:=nil;
p^.right:=nil;
end;


PROCEDURE insert(var p : PNode; h : integer);
begin
make(p^.left,Random(10){h});
make(p^.right,Random(10){h});
if h > 1 then
begin
insert(p^.left,h-1);
insert(p^.right,h-1);
end;
end;
{--------------------------------------------------------}
PROCEDURE inorder(var p : PNode);

begin
if p<>nil then
begin
inorder(p^.left);
Write(p^.key,' ');
inorder(p^.right);
end;
end;
{-----------------------------------------------------}
PROCEDURE poisk(var p : PNode; x : TKey; var k : Integer);
begin
if p<>nil then
begin
if p^.key = x then k:=k+1;
poisk(p^.left,x,k);
poisk(p^.right,x,k);
end;
end;
{******************************************}

{--------------------------------------------------------}
var p : PNode; x : Tkey;
h,kol : integer; tree : PNode;
begin
clrscr;
h:=2;
tree:=nil;
make(tree,Random(10){0});
insert(tree,h);
Writeln('obratnij obhod dereva: ');
inorder(tree);

Writeln;
Writeln;
Writeln('vvedite iskomij kluth : ');
Readln(x);
kol:=0;
poisk(tree,x,kol);

Writeln;
Write('thislo vhogdenij klutha ',x,': ',kol);

readln;
end.
Прикрепленный файл  DER.PAS ( 1.41 килобайт ) Кол-во скачиваний: 437


И ещё раз СПАСИБО wub.gif