бинарные деревья

[gilex]

"Составить программу, определяющую количество вершин к - того уровня бинарного дерева."
я формирую и вывожу дерево. ну вот сложность в том, что я и рекурсию пробовал и циклы всякие ничего неполучается а обход и подсчет количества вершин К-того уровня сделать не могу. вот фрагмент моей проги:

Program derevo;
Uses Crt;

Type inform = Integer;
ss = ^zveno;
zveno = Record
key: Integer;
inf: Inform;
left, right: ss;
End;

Var t:ss;
n,c,i,k: Integer;


{----формирование дерева----}

Procedure Vstavka (Var p: ss; x: Integer);
Begin
If p = Nil Then
Begin
New (p);
p^.inf:=x;
p^.key:=1;
p^.left:=Nil;
p^.right:=Nil;
End;
If x<p^.inf Then Begin Vstavka (p^.left,x); End;
If x>p^.inf Then Begin Vstavka (p^.right,x); End;
End;

{----вывод дерева----}

Procedure Print (Var p: ss; h: Integer);
Var i: Integer;
Begin
If p <> Nil Then
Begin
Print(p^.right,h+4);
For i:=1 To h Do Write (' ');
Writeln (p^.inf);
Print (p^.left,h+4);
End;
End;


Begin ClrScr;
Writeln ('Введите количество ключей дерева: ');
Readln (n);
Writeln ('Введите информ часть дерева: ');
For i:=1 To n Do
Begin
Read (с);
Vstavka (t,c);
End;
Print (t,c);
Writeln ('Введите уровень: ');
Readln (n);

А че тут дальше не пойму как реализовать. где-то в этой части проги должен быть подсчет количества вершин заданного уровня.

Readkey;
End.

подскажите пожалуйста. заранее благодарен.

[gilex]

ребят ну чего никто в деревьях не понимает?

[capta1n]

на самом деле если дерево полноценное, количество элементов на каждом уровне определяется как 2^K, где K - уровень дерева ( ^ - степень ) - допустим на 4 уровне будет 16 элементов ( при полноценном дереве ) - а вообще если равновесное дерево - это либо 2^K либо (2^K)-1 - ну потому что дерево может быть сформировано не до конца ( где K - последний уровень ) вот, а если дерево нестандартное, то надо думать

да - и корень дерева - это нулевой уровень

[gilex]

блин да я не на столько дебил чтобы не понять, что 2^К - это полноценное дерево. я вас и прошу помочь додумать как считать, если дерево не полноценное... пожалуйста скоро уже сдавать надо...

[Stepler]

Вот держы! А процедурка довольно таки просатя.

Program derevo;
Uses Crt;

Type inform = Integer;
ss = ^zveno;
zveno = Record
key: Integer;
inf: Inform;
left, right: ss;
End;

Var t:ss;
n,nn,c,i,k: Integer;

procedure pkv(tt:ss;nk:integer);
 begin
 if(nn=nk) then begin k:=k+1;;nn:=nn-1;exit;end;
 if(tt^.left<>nil)then begin nn:=nn+1;pkv(tt^.left,nk);end;
 if(tt^.right<>nil)then begin nn:=nn+1;pkv(tt^.right,nk);end;
 nn:=nn-1;
 end;
{----формирование дерева----}

Procedure Vstavka (Var p: ss; x: Integer);
Begin
If p = Nil Then
Begin
New (p);
p^.inf:=x;
p^.key:=1;
p^.left:=Nil;
p^.right:=Nil;
End;
If x<p^.inf Then Begin Vstavka (p^.left,x); End;
If x>p^.inf Then Begin Vstavka (p^.right,x); End;
End;

{----вывод дерева----}

Procedure Print (Var p: ss; h: Integer);
Var i: Integer;
Begin
If p <> Nil Then
Begin
Print(p^.right,h+4);
For i:=1 To h Do Write (' ');
Writeln (p^.inf);
Print (p^.left,h+4);
End;
End;


Begin ClrScr;
Writeln ('Vvedite koli4estvo klju4ej: ');
Readln (n);
For i:=1 To n Do
Begin
Read (c);
Vstavka (t,c);
End;
Print (t,c);
Writeln ('Vvedite urovenj: ');
Readln (n);
nn:=1;
k:=0;
pkv(t,n);
writeln('Koli4estvo vershun na ',n,' urovne = ',k);
Readkey;
End.

[gilex]

Stepler, большое тебе спасибо. все работает. завтра пойду сдавать))) разобрался... оказывается все было так просто... еще раз СПАСИБО)))

[ABTOPuTET]

Stepler.....////От меня тож огром пасиБ...ВЫРУЧИЛ
Респект те браТ.

[Mikheeva_Ksu]

Stepler, а не могли бы вы мне помочь? дано бинарное дерево, нужно подсчитать количество уровней в дереве и отдельно количество листьев?