[semplice] altezza albero ordinato

[Giova411]

Altezza è il massimo livello delle sue foglie, ma il seguente pseudocodice (dal testo) non mi convince

Codice:

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


[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
Sempre rimanendo negli Alberi Ordinati più generali con puntatore al primo figlio / fratello:
se volessi calcolare i nodi?
Uso sempre questa sorta di struttura?

Codice:

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?

Codice:

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!