www.MegaLab.it

da **morskott** » dom feb 22, 2004 4:11 pm

è una domanda stupida, ma come si fa a sapere il max numero contenuto nelle foglie di un albero binario???????
vi prego, non linciatemi per la banalità!!!!!!!

da **morskott** » dom feb 22, 2004 4:11 pm

è una domanda stupida, ma come si fa a sapere il max numero contenuto nelle foglie di un albero binario???????
vi prego, non linciatemi per la banalità!!!!!!!

da **Leo** » dom feb 22, 2004 5:43 pm

Se non mi ricordo male, il numero massimo di foglie di un albero binario è 2^(h-1) dove h è l'altezza dell'albero.

da **Ices_Eyes** » dom feb 22, 2004 5:50 pm

Per l'esattezza, sia h l'altezza dell'albero, se è un albero binario completo allora il numero di foglie è 2^h, se invece non è completo possono essere in numero differente...Ho fatto l'esame venerdì... [;)]

Ciao

da **Xerex** » dom feb 22, 2004 5:50 pm

Stai parlando del numero di foglie, o del massimo valore contenuto nelle foglie?

da **Ices_Eyes** » dom feb 22, 2004 5:57 pm

Ha ragione Xerex però...
Puoi fare così: vai alla prima foglia a sx, ti salvi il valore e poi scorri tutto l'albero modoficando quel valore se incontri una foglia con valore maggiore...Se invece l'albero ha proprietà particolari,tipo essere albero binario di ricerca o max-heap, o altro, allora è diverso e più semplice...Ciao [^]

da **morskott** » dom feb 22, 2004 7:56 pm

<blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da Xerex
 Stai parlando del numero di foglie, o del massimo valore contenuto nelle foglie?
<hr height="1" noshade id="quote"></blockquote id="quote">
ho un albero di interi e voglio sapere l'intero massimo contenuto nelle foglie

da **Zane** » dom feb 22, 2004 8:33 pm

Allora è molto più facile: è il numero contenuto nell'ultima foglia all'estrema destra.

da **Xerex** » dom feb 22, 2004 8:34 pm

<blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da morskott
 <blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da Xerex
 Stai parlando del numero di foglie, o del massimo valore contenuto nelle foglie?
<hr height="1" noshade id="quote"></blockquote id="quote">
ho un albero di interi e voglio sapere l'intero massimo contenuto nelle foglie
<hr height="1" noshade id="quote"></blockquote id="quote">

ah ecco...
bhe, se l'albero è un'albero di ricerca ti basta prendere la foglia "posizionata" più a destra.
Se invece non lo è, segui il metodo suggerito da ices_Eyes

da **Leo** » dom feb 22, 2004 8:48 pm

<blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da Ices_Eyes
 Per l'esattezza, sia h l'altezza dell'albero, se è un albero binario completo allora il numero di foglie è 2^h
<hr height="1" noshade id="quote"></blockquote id="quote">

Il tuo ragionamento sarebbe valido se nell'altezza non si contasse anche la radice. Ad esempio un albero alto 3 è fatto così:

O
/
O O
/ /
O O O O

Quindi come vedi le foglie sono 2^(h-1) ovvero 2^2.

<blockquote id="quote">citazione:<hr height="1" noshade id="quote">
ho un albero di interi e voglio sapere l'intero massimo contenuto nelle foglie
<hr height="1" noshade id="quote"></blockquote id="quote">

Ti chiedo scusa ma non l'avevo capito...
Comunque a questa pagina puoi trovare alcuni algoritmi per la visita degli alberi. In un modo simile puoi trovare il massimo delle foglie.
Ad esempio potresti sfruttare la funzione contafoglie, adattando la ricorsione alla ricerca del massimo.

da **Ices_Eyes** » dom feb 22, 2004 10:46 pm

<blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da Leo
 <blockquote id="quote">citazione:<hr height="1" noshade id="quote">Messaggio inserito da Ices_Eyes
 Per l'esattezza, sia h l'altezza dell'albero, se è un albero binario completo allora il numero di foglie è 2^h
<hr height="1" noshade id="quote"></blockquote id="quote">

Il tuo ragionamento sarebbe valido se nell'altezza non si contasse anche la radice. Ad esempio un albero alto 3 è fatto così:

O
/
O O
/ /
O O O O

Quindi come vedi le foglie sono 2^(h-1) ovvero 2^2.
<hr height="1" noshade id="quote"></blockquote id="quote">

Infatti a me quello lo hanno insegnato come alto 2 (altezza=cammino massimo dalla radice a una foglia, quindi in pratica solo i /)
Sarà variabile anche questa definizione...

Ciao

www.MegaLab.it

[JAVA] numero max delle foglie di un albero

[JAVA] numero max delle foglie di un albero

[JAVA] numero max delle foglie di un albero

Chi c’è in linea