domanda su albero binario

[melaniemellis]

supponiamo che un albero binario abbia tre livelli.Qual'è il numero massimo e minimo di nodi che può contenere?giustificare la risposta

[Amsirak]

Non so se tra i livelli si conta anche la radice, nel caso il numero massimo è 2^n - 1

[melaniemellis]

Originariamente inviato da Amsirak

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

[GTKM]

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.

[melaniemellis]

Originariamente inviato da GTKM

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

[GTKM]

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.)

[melaniemellis]

Originariamente inviato da GTKM

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

[melaniemellis]

perchè 2^2+1 -1 è due alla terza meno uno!ed è sette!

[GTKM]

Originariamente inviato da melaniemellis

sul nodo massimo però facendo 2^n+1 -1 esce 7 nodi

Certo, quando ho scritto "3" mi riferivo al numero minimo.

[melaniemellis]

Come esce il 3??

[melaniemellis]

ma un albero di 3 livelli vuol dire che ha altezza tre?quindi un albero di 4livelli ha altezza 4 e cosi via?

[GTKM]

Originariamente inviato da melaniemellis

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.

[melaniemellis]

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

[GTKM]

Originariamente inviato da melaniemellis

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

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.

Comunque, la cosa importante è che sia chiaro il concetto.