Date un occhiatina a questa semplice funzione...

[marcus81]

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...

[/\/\@®¢Ø]

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]

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]

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]

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...

[/\/\@®¢Ø]

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]

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]

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]

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]

Certo...tra l'altro è la stessa proposta da fabio309...tranne che per il -1...

[marcus81]

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