Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: AngyFio on 03-06-2010, 14:50:19



Title: Quiz su alberi
Post by: AngyFio on 03-06-2010, 14:50:19
Salve,

Nel sistema di esercitazione ci sono quesiti a risposta multipla del tipo: "Sia dato un albero binario completo contenente 8 nodi..."

Ma per albero binario completo si intende un albero binario i cui nodi abbiano o zero o due figli.

Dunque, come fa un albero binario completo ad avere un numero pari di nodi??  :boh



Title: Re:Quiz su alberi
Post by: XDnl on 03-06-2010, 15:27:04
Il testo dice anche "il cui ultimo livello è riempito da sinistra a destra".
L'albero in questione è il seguente (ogni O è un nodo)

                            O                <---- primo livello (radice)
                       O      O
                    O   O  O  O
                  O                          <---- ultimo livello riempito da sx verso dx

Diciamo che l'albero è completo escludendo eventualmente l'ultimo livello.
 .ciaociao


Title: Re:Quiz su alberi
Post by: AngyFio on 03-06-2010, 15:35:42
Il testo dice anche "il cui ultimo livello è riempito da sinistra a destra".
L'albero in questione è il seguente (ogni O è un nodo)

                            O                <---- primo livello (radice)
                       O      O
                    O   O  O  O
                  O                          <---- ultimo livello riempito da sx verso dx

Diciamo che l'albero è completo escludendo eventualmente l'ultimo livello.
 .ciaociao


Si in effetti l'esercizio l'ho risolto così...
Però quell'affermazione iniziale può far venire qualche dubbio  .penso


Title: Re:Quiz su alberi
Post by: LexaIdo on 03-06-2010, 17:41:59
se non mi sbaglio nella definizione di albero completo rientra pure il caso in cui l'ultimo livello è allineato a sinistra, cioè riempito da sinistra a destra...quindi anche quell'albero è da considerarsi un albero completo  :-OK


Title: Re:Quiz su alberi
Post by: AngyFio on 03-06-2010, 19:48:28
se non mi sbaglio nella definizione di albero completo rientra pure il caso in cui l'ultimo livello è allineato a sinistra, cioè riempito da sinistra a destra...quindi anche quell'albero è da considerarsi un albero completo  :-OK

Grazie questo non lo sapevo   .wink


Title: Re:Quiz su alberi
Post by: cock86 on 03-06-2010, 20:48:29
facciamo un pò di ordine!
Completo se tutte le foglie hanno altezza h o h-1 e tutti i nodi interni hanno grado(figli) due eccetto al più uno;
Pieno se le foglie hanno tutte altezza h e tutti i nodi hanno grado due;
Perfettamente bilanciato se ogni nodo è di grado due o zero;
Perfettamente bilanciato in altezza se ogni sotto albero sinistro e destro si differenziano al più di un livello.

Ho visto un pò di confusione in alcune affermazioni.
 .ciaociao


Title: Re:Quiz su alberi
Post by: AngyFio on 04-06-2010, 18:26:26
facciamo un pò di ordine!
Completo se tutte le foglie hanno altezza h o h-1 e tutti i nodi interni hanno grado(figli) due eccetto al più uno;
Pieno se le foglie hanno tutte altezza h e tutti i nodi hanno grado due;
Perfettamente bilanciato se ogni nodo è di grado due o zero;
Perfettamente bilanciato in altezza se ogni sotto albero sinistro e destro si differenziano al più di un livello.

Ho visto un pò di confusione in alcune affermazioni.
 .ciaociao

Grazie per il chiarimento...
Purtroppo nel libro non è spiegato così in dettaglio  .wink

A presto .ciaociao