Pages: [1]   Go Down
Print
Author Topic: Quiz su alberi  (Read 1699 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
AngyFio
Matricola
*
Offline Offline

Posts: 29


« 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

Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #1 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.
 
Logged
AngyFio
Matricola
*
Offline Offline

Posts: 29


« Reply #2 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.
 


Si in effetti l'esercizio l'ho risolto così...
Però quell'affermazione iniziale può far venire qualche dubbio 
Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #3 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
Logged
AngyFio
Matricola
*
Offline Offline

Posts: 29


« Reply #4 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   
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #5 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.
 
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
AngyFio
Matricola
*
Offline Offline

Posts: 29


« Reply #6 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.
 

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

A presto
Logged
Pages: [1]   Go Up
Print
Jump to: