Esercizio Algoritmi e Strutture Dati

[AAnto]

Ciao a tutti...
se non è questa la sezione giusta, vi prego di perdonarmi...

Allora, sto studiando per l'esame di Algoritmi e sto svolgendo i primi esercizi sugli alberi binari.

Esempio questo:
"Si progetti un algoritmo che dato un albero binario, calcoli l'altezza del sotto albero radicato nel figlio di sinistra della radice".

Il mio problema risiede nel capire come valutare l'altezza del sotto albero del figlio di sx.
Per calcolare l'altezza di un albero completo riesco. In effetti per gli alberi binari si può implementare un algoritmo ricorsivo che si basa sulla tecnica del Divide et Impera..

Ad esempio (per l'albero intero):

altezza(u):
if(u==null)
return -1;
else
return 1 + max(altezza(u.sx), altezza(u.dx))

Ma non saprei come considerare solo il sotto albero del figlio sx.
Potreste aiutarmi?

[vict85]

L'algoritmo è lo stesso, solo che invece di partire da \(u\) parti da \(u.sx\).

[AAnto]

Cioè:

altezza(u.sx):
if(u.sx==null)
return -1;
else
return 1 + max(altezza(?), altezza(?))


Cosa metto al posto di ?

[vict85]

In che linguaggio lo stai scrivendo? Comunque sarebbe qualcosa come:

Codice:

def altezza( u ):
    if( u == null )
        return -1
    return 1 + max( altezza( u.sx ), altezza( u.dx ) )

def altezza_sub_sx( u ):
    if( u == null )
        return -1
    return altezza( u.sx )

P.S.: Ti suggerisco di usare il tag code:

Codice:

[code]Il codice va qui[/code]

[AAnto]

Pseudo codice C...
solo che non sto riescendo a capire

[vict85]

Cosa non capisci? Come calcoleresti quell'altezza a mano?

[Raptorista]

Moderatore: Raptorista

Sposto da Analisi numerica.

Ti stai perdendo in un bicchiere d'acqua.

• Hai una funzione che calcola l'altezza di un albero.
• "il sotto albero del figlio sx" è un albero.