Współczynnik zagęszczenia drzewa to stosunek liczby węzłów do wysokości drzewa. Napisać funkcję, która dla danego drzewa binarnego zwróci wskaźnik do wierzchołka jego poddrzewa o największym współczynniku zagęszczenia.
Typ wskaźnikowy jest taki:
Kod: Zaznacz cały
type wsk=^wierzcholek;
wierzcholek=record
klucz:integer;
lewy,prawy,ojciec:wsk
end
Kod: Zaznacz cały
procedure wspolczynnik (r:wsk; var: n,h:integer, v:wsk;);
var
a,b,c:real;
nl,np,hl,hp:integer;
vl,vp: wsk;
begin
if r=nil then
h:=0;
n:=0;
v:=nil;
end
else
begin
wspolczynnik (r^.prawy,np,hp,vp);
wspolczynnik (r^.lewy,nl,hl,vl);
n:=np+nl+1;
if hl>hp then h:=hl+1 else h:=hp+1;
a:=nl div hl;
b:=np div hp;
c:=n div h;
if a>b then
begin
if c+1>a then v:=r else v:=vp;
end
else
begin
if c+1>b then v:=r else v:=vp;
end;
end;
end.
function najwiekszy(r:wsk; var:n,h:integer;v:=wsk):wsk;
begin
wspolczynnik(r,n,h,v);
najwiekszy:=v;
end