[semplice] altezza albero ordinato

Giova411
Altezza è il massimo livello delle sue foglie, ma il seguente pseudocodice (dal testo) non mi convince :smt012
profond(Tree t)
integer max <-- 0
Tree u <-- t.leftmostChild()  % primo figlio (a sx)
while u != nil do
  integer t <-- profond(u) + 1
  if t > max then max <-- t
  u <-- u.rightSibling()  % prossimo fratello (da sx a dx)
return max

Risposte
onlyReferee
Ciao Giova411 :!:
E' corretto. Se ci pensi bene ad ogni chiamata ricorsiva è come se avessi un nuovo albero di cui determinare l'altezza. Quella massima viene poi aggiornata solo quando quella corrente è maggiore di essa. rightSibling poi ti restituisce il puntatore al successivo sottoalbero il cui nodo radice è fratello del nodo radice dell'albero corrente.
Questo algoritmo potrebbe essere semplificato nel caso di un albero binario ma ovviamente tale procedura è generica e funziona con un albero $n$-ario.

Giova411
Ciao bello!
Sì pensavo al ciclo while: se ha molti fratelli sballa il conteggio. Che dici?

Giova411
Only perdonami,
perchè sono così "automa" =) da vedere sballato quel while?
Cioé, se punta a troppi fratelli, non conteggia in "orizzontale" rimanendo nel while e sommando di uno?
Ma qui noi vogliamo l'altezza. Il rightSiblig è sempre buttato in u che poi viene controllato dal ciclo...
Dove sbaglio ragionamento secondo te?
grazie mille prima di tutto!

onlyReferee
No, se rimane nel ciclo while non c'è il rischio che conteggi più elementi del dovuto per l'altezza ($\max$ viene riaggiornato a $0$ ad ogni chiamata della funzione).

Giova411
Mi sto convincendo ma preferisco gli alberi binari :-D
Sempre rimanendo negli Alberi Ordinati più generali con puntatore al primo figlio / fratello:
se volessi calcolare i nodi?
Uso sempre questa sorta di struttura?
contaNodi(Tree t)
 tot <-- 1
 Tree s <-- t.leftmostChild()
 while ( s != nil ) do
    tot <-- tot + contaNodi(s)
    s <-- s.rightSibling()
 return tot


Pure per contare le foglie?

contaFoglie(Tree s)
 if (s.leftmostChild = nil) return 1
 tot <-- 0
 Tree t <-- s.leftmostChild()
 while ( t != nil ) do
    tot <-- tot + contaFoglie(t)
    t <-- t.rightSibling()
 return tot


:? :? :? :?

onlyReferee
Nel primo caso è corretto, considera però che l'assunzione deve essere che l'albero non è vuoto (ossia il nodo radice non lo deve essere altrimenti va in errore).
Nel secondo caso vale lo stesso discorso fatto per il primo. E' corretto considerando la struttura dati utilizzata poiché, avendo il puntatore solo al figlio più a sinistra se il nodo corrente ha questi settato a nil allora siamo sicuri che non ha discendenti e pertanto è un nodo foglia.
Eh, lo so, gli alberi binari sono più semplici da comprendere e trattare e soprattutto su di essi si possono eseguire moltissime importanti considerazioni.

Giova411
Grazie mille OnlyReferee!

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.