melaniemellis
16-06-2015, 18:04
supponiamo che un albero binario abbia tre livelli.Qual'è il numero massimo e minimo di nodi che può contenere?giustificare la risposta
View Full Version : domanda su albero binario
Amsirak
16-06-2015, 18:24
Non so se tra i livelli si conta anche la radice, nel caso il numero massimo è 2^n - 1
melaniemellis
16-06-2015, 18:32
Non so se tra i livelli si conta anche la radice, nel caso il numero massimo è 2^n - 1
si,ok questo mi torna mi viene 2^3 -1,il valore minimo invece non riesco a capire se è n + 1 o solamente n
si,ok questo mi torna mi viene 2^3 -1,il valore minimo invece non riesco a capire se è n + 1 o solamente n
GTKM
16-06-2015, 18:52
Un albero binario completo di altezza n (per intenderci, significa che hai la radice, e poi altri n "livelli"), ha 2^n foglie e 2^n - 1 nodi interni.
Il minimo valore di nodi, invece, si ottiene quando ogni nodo ha un solo figlio, quindi, in pratica, puoi vederlo come una lista. Dunque, avrà 1 foglia e n nodi interni.
Il minimo valore di nodi, invece, si ottiene quando ogni nodo ha un solo figlio, quindi, in pratica, puoi vederlo come una lista. Dunque, avrà 1 foglia e n nodi interni.
melaniemellis
16-06-2015, 19:10
Un albero binario completo di altezza n (per intenderci, significa che hai la radice, e poi altri n "livelli"), ha 2^n foglie e 2^n - 1 nodi interni.
Il minimo valore di nodi, invece, si ottiene quando ogni nodo ha un solo figlio, quindi, in pratica, puoi vederlo come una lista. Dunque, avrà 1 foglia e n nodi interni.
quindi essendo che ogni livello deve avere almeno un nodo,vuol dire che il numero minimo è n
Il minimo valore di nodi, invece, si ottiene quando ogni nodo ha un solo figlio, quindi, in pratica, puoi vederlo come una lista. Dunque, avrà 1 foglia e n nodi interni.
quindi essendo che ogni livello deve avere almeno un nodo,vuol dire che il numero minimo è n
GTKM
16-06-2015, 19:16
Esattamente. Infatti, un albero di altezza 3 ha 3 nodi più una foglia.
(Ricordo che l'altezza dell'albero si calcola usando come livello "0" la radice.)
(Ricordo che l'altezza dell'albero si calcola usando come livello "0" la radice.)
melaniemellis
16-06-2015, 19:24
Esattamente. Infatti, un albero di altezza 3 ha 3 nodi più una foglia.
(Ricordo che l'altezza dell'albero si calcola usando come livello "0" la radice.)
sul nodo massimo però facendo 2^n+1 -1 esce 7 nodi
(Ricordo che l'altezza dell'albero si calcola usando come livello "0" la radice.)
sul nodo massimo però facendo 2^n+1 -1 esce 7 nodi
melaniemellis
16-06-2015, 19:26
perchè 2^2+1 -1 è due alla terza meno uno!ed è sette!
GTKM
16-06-2015, 19:46
sul nodo massimo però facendo 2^n+1 -1 esce 7 nodi
Certo, quando ho scritto "3" mi riferivo al numero minimo. :D
Certo, quando ho scritto "3" mi riferivo al numero minimo. :D
melaniemellis
16-06-2015, 19:52
Come esce il 3??:muro:
melaniemellis
16-06-2015, 19:54
ma un albero di 3 livelli vuol dire che ha altezza tre?quindi un albero di 4livelli ha altezza 4 e cosi via?
GTKM
16-06-2015, 20:11
ma un albero di 3 livelli vuol dire che ha altezza tre?quindi un albero di 4livelli ha altezza 4 e cosi via?
Altezza 3 significa che ci sono la radice più altri 3 livelli. Quindi, se h è l'altezza della radice, e n il numero totale di nodi e foglie, si hai n = 2^(h+1) - 1.
Se quando parli di un albero a 3 livelli, intendi la radice più altri due, allora l'albero ha altezza 2, e quindi n = 2^(2+1) - 1, cioè 7.
Il numero minimo di nodi, invece, è molto più facile da ricavare: n = h+1. Nel caso specifico, se hai 3 livelli (al solito, la radice più altri due), il numero minimo di nodi (includendo pure l'unica foglia), è n=3.
Spero di essere stato chiaro. :D
Altezza 3 significa che ci sono la radice più altri 3 livelli. Quindi, se h è l'altezza della radice, e n il numero totale di nodi e foglie, si hai n = 2^(h+1) - 1.
Se quando parli di un albero a 3 livelli, intendi la radice più altri due, allora l'albero ha altezza 2, e quindi n = 2^(2+1) - 1, cioè 7.
Il numero minimo di nodi, invece, è molto più facile da ricavare: n = h+1. Nel caso specifico, se hai 3 livelli (al solito, la radice più altri due), il numero minimo di nodi (includendo pure l'unica foglia), è n=3.
Spero di essere stato chiaro. :D
melaniemellis
16-06-2015, 20:16
Ah ok,si perfetto,ho capito!!..Eh no ma infatti non so se per tre livelli l'esercizio intende la radice compresa o no..Grazie mille:D
GTKM
16-06-2015, 20:21
Ah ok,si perfetto,ho capito!!..Eh no ma infatti non so se per tre livelli l'esercizio intende la radice compresa o no..Grazie mille:D
Per non confonderti riguardo l'altezza di un albero, ricorda che, in pratica, essa è data dal numero di archi che devi attraversare per arrivare dalla radice al nodo interessato. :D
Comunque, la cosa importante è che sia chiaro il concetto. :)
Per non confonderti riguardo l'altezza di un albero, ricorda che, in pratica, essa è data dal numero di archi che devi attraversare per arrivare dalla radice al nodo interessato. :D
Comunque, la cosa importante è che sia chiaro il concetto. :)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.