[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:


mi pare che non funzioni....

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

Grazie
Andrea

[71104]

nel caso base deve ritornare 0, non -1

[^TiGeRShArK^]

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

[D4rkAng3l]

Originariamente inviato da ^TiGeRShArK^

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!
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!
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]

Originariamente inviato da 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 -_-

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

[PGI-Bis]

Originariamente inviato da 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!
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. .

[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]

Originariamente inviato da Obinna

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

[wingman87]

Provo a dare anch'io una mia versione alla "olé"
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 .

[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;
}