[Pascal] Współczynnik zagęszczenia drzewa BST

Humanista123
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 1 sty 2017, o 20:32
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 17 razy

[Pascal] Współczynnik zagęszczenia drzewa BST

Post autor: Humanista123 »

Witajcie, mam zadanie:

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

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
Czy to jest dobrze? Proszę o pomoc.
karakuku
Użytkownik
Użytkownik
Posty: 226
Rejestracja: 14 sie 2016, o 17:31
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 20 razy
Pomógł: 60 razy

Re: [Pascal] Współczynnik zagęszczenia drzewa BST

Post autor: karakuku »

1.Ta funkcja:

Kod: Zaznacz cały

function najwiekszy(r:wsk):boolean;
begin
wspolczynnik(r,n,h,v);
najwiekszy:=v;
end
Nie odpali, bo nie ma deklaracji co to jest r,n,h,v. Poza tym funkcja "najwiekszy" powinna być typu wskaźnikowego, a nie boolean.

2.

Kod: Zaznacz cały

a:=nl div hl;
tutaj a:real, więc zamiast div można wstawić zwykłe dzielenie /

3.Dlaczego tu jest c+1?

Kod: Zaznacz cały

if a>b then
        begin
        if c+1>a then v:=r else v:=vp;
        end
Humanista123
Użytkownik
Użytkownik
Posty: 54
Rejestracja: 1 sty 2017, o 20:32
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 17 razy

Re: [Pascal] Współczynnik zagęszczenia drzewa BST

Post autor: Humanista123 »

karakuku pisze: 3.Dlaczego tu jest c+1?

Kod: Zaznacz cały

if a>b then
        begin
        if c+1>a then v:=r else v:=vp;
        end
Racja mój błąd -- 18 sie 2017, o 15:43 --Wielkie dzięki
karakuku
Użytkownik
Użytkownik
Posty: 226
Rejestracja: 14 sie 2016, o 17:31
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 20 razy
Pomógł: 60 razy

Re: [Pascal] Współczynnik zagęszczenia drzewa BST

Post autor: karakuku »

A no i a to zagęszczenie lewego poddrzewa więc powinno być

Kod: Zaznacz cały

if a>b then
        begin
        if c>a then v:=r else v:=vl;
        end
ODPOWIEDZ