[Pascal] Drzewo BST-istnienie węzła

[Humanista123]

Witajcie. Mam takie zadanie: Napisz funkcję, która sprawdzi, czy w drzewie binarnym istnieje taki węzeł, że w jego lewym niepustym poddrzewie jest tyle samo węzłów co w prawym.

Typ wskaźnikowy, to chyba (egzamin będę pisał na kartce, a nie na kompilatorze )

Kod: Zaznacz cały

type wsk=^wierzcholek;
wierzcholek=record
klucz:integer;
lewy,prawy,ojciec:wsk
end

Kod programu

Kod: Zaznacz cały

procedure drzewo (r:wsk; var h,a:integer);
var 
hl, hp, al, ap:integer;
begin
if r=nil then 
    begin 
    h:=0;
    a:=0;
    end;
else
    begin
    drzewo(r^.lewy;hl;al);
    drzewo(r^.prawy;hp;ap);
    h:=hl+hp+1;
    if hl=hp and hl<>0 then a:=al+ap+1
    else
    a:=al+ap;
    end;
end.

function sprawdz (r:wsk):boolean;
begin
drzewo (r,h,a);
if a>0 then sprawdz:=true
else 
sprawdz:=false;
end.

Czy to jest dobrze? Uprzejmie proszę o pomoc

[karakuku]

Tu

Kod: Zaznacz cały

drzewo(r^.lewy;hl;al);

wywołujesz procedurę, a zmienna hl ani al nie ma wartości. Poza tym powinny być przecinki zamiast średników przy wywoływaniu.

Tutaj

Kod: Zaznacz cały

function sprawdz (r:wsk):boolean;
begin
drzewo (r,h,a);
if a>0 then sprawdz:=true
else 
sprawdz:=false;
end.

h i a nie ma wartości, a nawet nie jest zadeklarowane.

Ukryta treść:    

Ja bym sugerował tą procedurę "drzewo" zrobić procedurą wewnętrzną funkcji "sprawdz". Wtedy można w ogóle pozbyć się tych zmiennych a, al i ap. I zrobić zamiast:

Kod: Zaznacz cały

if hl=hp and hl<>0 then a:=al+ap+1
    else
    a:=al+ap;

to

Kod: Zaznacz cały

if hl=hp and hl<>0 then sprawdz:=true

[Humanista123]

Dziękuję za odpowiedź.

wywołujesz procedurę, a zmienna hl ani al nie ma wartości. Poza tym powinny być przecinki zamiast średników przy wywoływaniu.

Hmmm... Jak to zrobić? Skoro mam tutaj rekurencję. Myślałem, że się będzie zamieniało h na hl, jeśli to h jest lewym synem i h na hp, jeśli jest prawym synem. Jak w takim razie to zrobić?

[karakuku]

W sumie to chyba jak napiszesz var x:integer to domyślnie x=0, więc w tym wypadku będą miały wartość 0 ale dla pewności lepiej im dać jakąś początkową wartość.
Można to zrobić tak:

Ukryta treść:    

Kod: Zaznacz cały

procedure drzewo (r:wsk; var h,a:integer);
var 
hl, hp, al, ap:integer;
begin
if r=nil then 
    begin 
    h:=0;
    a:=0;
    end;
else
    begin
    hl:=0; al:=0 ; hp:=0; ap:=0; //
    drzewo(r^.lewy;hl;al);
    drzewo(r^.prawy;hp;ap);
    h:=hl+hp+1;
    if hl=hp and hl<>0 then a:=al+ap+1
    else
    a:=al+ap;
    end;
end.

h się w nic nie zmienia.

Ja bym tak to zmienił żeby było trochę prościej:

Ukryta treść:    

Kod: Zaznacz cały

function sprawdz (r:wsk):boolean;
procedure drzewo (r:wsk; h:integer);
var hl, hp:integer;
begin
if r=nil then 
    begin 
    h:=0;
    end
else
    begin
    hl:=0; hp:=0;
    drzewo(r^.lewy,hl);
    drzewo(r^.prawy,hp);
    h:=hl+hp+1;
    if hl=hp and hl<>0 then sprawdz:=true;
    end;
end;


begin
sprawdz:=false;
drzewo (r,0);
end

[Humanista123]

Ale wtedy to za każdym razem jak wejdziemy do procedury, to hl, hp, ap, al, bedzie nam sie zerować.

A w tym twoim programie, to gdzie zmiennym hl, hp przypisałeś wartość?

[karakuku]

A w tym twoim programie, to gdzie zmiennym hl, hp przypisałeś wartość?

Zapomniałem Już poprawiam

Ale wtedy to za każdym razem jak wejdziemy do procedury, to hl, hp, ap, al, bedzie nam sie zerować.

To są wewnętrzne zmienne procedury, jak wchodzisz "głębiej" rekurencją to już to hl nie zmienia hlów z poprzednich procedur. Z każdą nową rekurencyjnie odpaloną procedurą na nowo robisz var hp,hl,... ( co prawdopodobnie za każdym razem i tak ustawia te zmienne na wartość 0)

[Humanista123]

Aaaaa, ok, faktycznie. Rozumiem. Wielkie dzięki -- 18 sie 2017, o 17:04 --Ale mogę te wartości przypisać chyba także po if r=nil, tak?

[karakuku]

Możesz ale po co? Jeśli r=nil to w ogóle nie będziemy potrzebowali tych zmiennych.