PDA

View Full Version : Date un occhiatina a questa semplice funzione...

marcus81
27-05-2003, 20:17
Salve ragazzi ho implementato questa funzione per determinare la profonditą di un albero binario, il codice č pascal:function

function profondita_albero(p: nodo): integer;
begin
if p <> NIL then
if (p^.sx <> NIL) or (p^.dx <> NIL) then
profondita_albero:=max(profondita_albero(p^.sx), profondita_albero(p^.dx))+1;
end;

cos'ha che non va visto che mi da risultati assurdi?Grazie ;)
PS: se tolgo il controllo sull'albero dx e sx e lascio solo p <> NIL funziona ma mi dą la profonditą maggiorata di 1...
/\/\@®¢Ų
28-05-2003, 00:53
Il primo consiglio che ti do e' quello di scrivere il codice tra e per evitare di perdere la formattazione D ;)
Il secondo e' di controllare cosa restituire quando p = NIL, fatto questo puoi tranquillamente togliere il secondo controllo.
fabio309
28-05-2003, 08:55
prova con questo...che č molto simile


if p<>nil then
profondita_albero:=max(profondita_albero(p^.sx), profondita_albero(p^.dx))+1;
else
profondita_albero:=0;


non ricordo bene la sintassi del pascal, vedi un pņ come aggiustarlo

Ciao ciao
cionci
28-05-2003, 09:12
function profondita_albero(p: nodo): integer;
begin
if p <> NIL then
if (p^.sx <> NIL) or (p^.dx <> NIL) then
profondita_albero:=max(profondita_albero(p^.sx), profondita_albero(p^.dx))+1;
end;

Manca la condizione di arresto...cioč se p = NIL devi ritornare 0...a quel punto l'if sul valore del punt. di sx e di dx non ha senso metterlo...
Il codice postato da fabio309 va benissimo...

Fare una funzione ricorsiva č molto simile a fare una dimostrazione per induzione... Prima metti la condizione di arresto (quando la ricorsione deve terminare)... Poi ti immagini di essere ad un nodo generico della tua struttura e scrivi il codice relativo a come devi comportarti in quel caso (senza fare supposizioni sulla forma della struttura)...
E dopo la funzione viene da sč...
marcus81
28-05-2003, 11:47
Dunque il problema non č che la procedura non funziona(la condizione d'arresto č "if p<>NIL", aggiungendo il ramo else ovviamente ci assicuriamo che passando un albero vuoto la procedura ritorni 0 com'č giusto che sia...
Forse mi spiego meglio con una figura:
guardate l'albero allegato...la procedura, passata la radice di tale albero dovrebbe restituirmi una profonditą pari a 2, invece restituisce 3, per questo avevo aggiunto la condizione if (p^.sx <> NIL) or (p^.dx <> NIL) in modo tale che venga richiamata solo quando il nodo ha almeno un figlio...ma non vuole saperne di funzionare e dą risultati sballati...
/\/\@®¢Ų
28-05-2003, 11:51
Originally posted by "marcus81"

Dunque il problema non č che la procedura non funziona(la condizione d'arresto č "if p<>NIL", aggiungendo il ramo else ovviamente ci assicuriamo che passando un albero vuoto la procedura ritorni 0 com'č giusto che sia...
Forse mi spiego meglio con una figura:
guardate l'albero allegato...la procedura, passata la radice di tale albero dovrebbe restituirmi una profonditą pari a 2, invece restituisce 3, per questo avevo aggiunto la condizione if (p^.sx <> NIL) or (p^.dx <> NIL) in modo tale che venga richiamata solo quando il nodo ha almeno un figlio...ma non vuole saperne di funzionare e dą risultati sballati...
L'errore e' proprio il caso p = NIL !
Se ho un puntatore a NIL non ho un albero di altezza zero ! L'albero di altezza zero ce l'ho quando ho un solo nodo (una foglia). La soluzione e' quindi ritornare -1 quando ho un puntatore nullo (in quel modo le foglie ritornano max(-1,-1) + 1 ovvero 0 )
cionci
28-05-2003, 15:26
Originally posted by "/\/\@®¢Ų"


Se ho un puntatore a NIL non ho un albero di altezza zero ! L'albero di altezza zero ce l'ho quando ho un solo nodo (una foglia). La soluzione e' quindi ritornare -1 quando ho un puntatore nullo (in quel modo le foglie ritornano max(-1,-1) + 1 ovvero 0 )
Questo non me lo ricordavo...credevo che altezza zero implicasse l'albero vuoto...
cionci
28-05-2003, 15:32
Originally posted by "marcus81"

Dunque il problema non č che la procedura non funziona(la condizione d'arresto č "if p<>NIL", aggiungendo il ramo else ovviamente ci assicuriamo che passando un albero vuoto la procedura ritorni 0 com'č giusto che sia...
La condizione di arresto non p <> NIL, ma p == NIL...e non č la stessa cosa perchč nel modo in cui l'hai fatto te la condizione di arresto č il ramo else... Con l'if che hai messo te che controlla il figlio di dx e il figlio di sx non č una condizione di arresto...anche perchč nel caso che solo uno dei due puntatori sia NIL viene richiamata la funzione passandogli un puntatore NIL e la tua funzione non gestisce questo caso... Inoltre nel caso che uno dei due puntatori sia NIL profondita_albero non ha un valore di ritorno valido...a meno che il Pascal non gli assegni zero di default...
goldorak
28-05-2003, 17:46
Secondo me una soluzione potrebbe essere :

function profondita_albero(p:^nodo):integer;
begin
if p==NIL then profondita_albero:= -1
else profondita_albero:=max(profondita_albero(p^.sx),profondita_albero(p^.dx))+1;
end
cionci
28-05-2003, 17:52
Certo...tra l'altro č la stessa proposta da fabio309...tranne che per il -1...
marcus81
28-05-2003, 23:23
Originally posted by "/\/\@®¢Ų"


L'errore e' proprio il caso p = NIL !
Se ho un puntatore a NIL non ho un albero di altezza zero ! L'albero di altezza zero ce l'ho quando ho un solo nodo (una foglia). La soluzione e' quindi ritornare -1 quando ho un puntatore nullo (in quel modo le foglie ritornano max(-1,-1) + 1 ovvero 0 )
La soluzione proposto dal mio omonimo funziona a meraviglia.Thanks ;)
Grazie a tutti per essere sempre disponibili ;)