[Pseudo Codice]Calcolare l'altezza di un albero (help me)

[D4rkAng3l]

Ciao,
stò un po' in crisi con un algoritmo trovato sulle dispense del professore per calcolare l'altezza di un albero...non mi torna.

L'algoritmo in pseudo codice è questo:


CalcolaAltezza(nodo r)
IF (r == null) THEN return(-1)

sin = CalcolaAltezza(figlio sinistro di r)
des = CalcolaAltezza(figlio destro di r)
return 1 + max{sin, des}


Per esempio se considero il seguente albero:
http://www.siatec.net/andrea/uni/easd/albero.jpg

mi pare che non funzioni....

non riesco a vedere quale sia l'ordine delle chiamate riorsive...mi date una mano? :cry:

Grazie
Andrea

[71104]

nel caso base deve ritornare 0, non -1

[^TiGeRShArK^]

http://noielambiente.altervista.org/piante/x.gif

Misurare un albero non è facile!

Esiste però un procedimento matematico che ci permette di ottenere una misura abbastanza precisa senza dover usare scale o chissà che altro.

Mettiti alla fine dell'ombra di un albero.
Con un sasso segna questo punto (B) e con un altro sasso segna il punto in cui finisce la tua ombra (D).

Misura la lunghezza dell'ombra dell'albero e della tua ombra, cioè i segmenti AB e CD.
Ora moltiplica la lunghezza dell'ombra dell'albero con la tua altezza, quindi dividi il prodotto ottenuto con la lunghezza della tua ombra.
Il risultato di questa espressione è l'altezza dell'albero!

In pratica:
AF = (AB X CE) : CD

:O



:asd::asd::asd::asd::asd:

[D4rkAng3l]

http://noielambiente.altervista.org/piante/x.gif

:O



:asd::asd::asd::asd::asd:

Geniale ahaha...e se all'esame gli trascrivo anche questa cosa hauhua

[Obinna]

Qualcuno di voi sarebbe in grado di scrivere lo stesso algoritmo ma in modo iterativo?? Ho un Albero Binario di Ricerca e devo calcolarne l'altezza obblogatoriamnete in modo iterativo....help me! :muro:
Grazie
Luca

[Obinna]

Qualcuno di voi sarebbe in grado di scrivere lo stesso algoritmo ma in modo iterativo?? Ho un Albero Binario di Ricerca e devo calcolarne l'altezza obblogatoriamnete in modo iterativo....help me! :muro:
Grazie
Luca

[Kenger]

Allora, l'ordine delle chiamate ricorsive è il seguente:

A B D F D B E B A C A.

Nel tuo caso l'algoritmo si sposta a sinistra fino ad arrivare all'ultimo nodo (F). Poi si sposta ancora a sinistra, non c'è nessun nodo e quindi la funzione ritorna -1 e siamo di nuovo in F. Poi si sposta a destra, non esiste nessun nodo e ritorna -1. Ora deve ritornare F. Ritorna 1+max(-1,-1) quindi ritorna 0. Va su D, si sposta a destra, non esiste nessun nodo e quindi ritorna -1. Ora deve ritornare D, che ritornerà 1+max(0,-1) che fà 1. E così via.

EDIT: Non avevo visto che era un grave digging -_-

[D4rkAng3l]

Allora, l'ordine delle chiamate ricorsive è il seguente:

A B D F D B E B A C A.

Nel tuo caso l'algoritmo si sposta a sinistra fino ad arrivare all'ultimo nodo (F). Poi si sposta ancora a sinistra, non c'è nessun nodo e quindi la funzione ritorna -1 e siamo di nuovo in F. Poi si sposta a destra, non esiste nessun nodo e ritorna -1. Ora deve ritornare F. Ritorna 1+max(-1,-1) quindi ritorna 0. Va su D, si sposta a destra, non esiste nessun nodo e quindi ritorna -1. Ora deve ritornare D, che ritornerà 1+max(0,-1) che fà 1. E così via.

EDIT: Non avevo visto che era un grave digging -_-

Doh cosa hai riesumato...dell'anno scorso...e pensare che questo esame di algoritmi ancora nonsono riuscito a darlo e probabilmente non lo darò neanche questo semestre che ne devo dare altri 5 :muro:

[PGI-Bis]

Qualcuno di voi sarebbe in grado di scrivere lo stesso algoritmo ma in modo iterativo?? Ho un Albero Binario di Ricerca e devo calcolarne l'altezza obblogatoriamnete in modo iterativo....help me! :muro:
Grazie
Luca

A naso (cioè senza rispolverare il libro di algoritmi e strutture dati):

P è una pila di nodi, P.push(radice), L = 1
finchè P è non vuota
n = P.pop()
L++
se n.dx = null L-- altrimenti L++, P.push(n.dx)
se n.sx = null L-- altrimenti L++, P.push(n.sx)
L è l'altezza

Forse. :D.

[Obinna]

Ho scritto il codice java secondo il tuo esempo, questo è il risultato:

private int gethigh (BinNode<Integer> node){

if(node != null){
int h = 1;
Stack<BinNode<Integer>> pila = new Stack<BinNode<Integer>>();
pila.push(node);
while(!(pila.isEmpty())){
node = pila.pop();
h++;
if(node.left == null) h--;
else { h++;
pila.push(node.left);
}
if(node.right == null) h--;
else { h++;
pila.push(node.right);
}
}
return h;
}
else return 0;
}

però per come l'ho scritto io non restituisce il valore giusto...
Quancuno sa dove si annida l'errore?!?!?!!?!?

[DanieleC88]

Secondo me per farlo iterativamente la cosa più facile è fare una visita per livelli (con una coda) e presupporre che l'albero sia completo:
Iterative-Tree-Height(T)
{
Levels = 0
Q = new Queue()

if (T == null)
{
return 0
}

Push(Q, T)

while (not Empty(Q))
{
Count = 0

while (Count < (2 ^ Levels))
{
x = Pop(Q)

if (x == null)
{
Push(Q, null)
Push(Q, null)
}
else
{
Push(Q, x->Left)
Push(Q, x->Right)
}

Count += 1
}

Levels += 1
}

return (Levels + 1)
}

Più o meno una cosa del genere... non l'ho testata, prendila con le pinze.
Notte. ;)

[PGI-Bis]

Ho scritto il codice java secondo il tuo esempo, questo è il risultato:


però per come l'ho scritto io non restituisce il valore giusto...
Quancuno sa dove si annida l'errore?!?!?!!?!?

Tieni conto che l'algoritmo che ho incollato potrebbe benissimo essere una putt@n@t@ colossale. L'ho scritto veramente alla "olè" :D. In teoria conta i passi che fa l'attraversamento. Ogni volta che scende aumenta di uno, ogni volta che sale diminuisce di uno. Forse funziona.

Ti conviene dare un'occhiata a qualcosa di più serio se vuoi evitare grandi sorprese all'esame :D.

[wingman87]

Provo a dare anch'io una mia versione alla "olé" :D
In pseudocodice:

int altezza=-1;
Se radice è null ritorna altezza;
Coda c=Coda vuota;
Aggiungi a c la radice;
int nElLivello=1; //numero di elementi del livello corrente che devo visitare
Finché c non è vuota{
Nodo n= estrai da c;
se c.left non è null aggiungilo a c;
se c.right non è null aggiungilo a c;
nElLivello--;
se nElLivello=0{
nElLivello= numero di elementi in c;
altezza++;
}
}
ritorna altezza;

Mi sembra corretto comunque...

[PGI-Bis]

Il mio algorrendo sembra contare una volta di troppo la discesa. Pare che si aggiusti dicendo:

P è una pila di nodi, P.push(radice), L = 1
finchè P è non vuota
n = P.pop()
L++
plus = 1;
se n.dx = null L-- altrimenti L += plus, P.push(n.dx), plus = 0
se n.sx = null L-- altrimenti L += plus, P.push(n.sx)
L è l'altezza

ma così facendo non sono più tanto sicuro del perchè dovrebbe funzionare :D.

[Vincenzo1968]

Questa è la mia versione iterativa, in C:


int TreeDepth(Tree *head)
{
Tree *temp1, *temp2;

int Conta;

Tree *stack[MAX_STACK];
int top;

top = 0;
Conta = 0;

if ( head == NULL )
{
return -1;
}

temp1 = temp2 = head;

while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
{
stack[top++] = temp1;
if ( Conta < top )
Conta++;
}

while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
if ( top == 0 )
return Conta;
temp1 = stack[--top];
}

stack[top++] = temp1;
temp1 = temp1->right;
if ( Conta < top )
Conta = top;
}

return Conta + 1;
}