Ciao a tutti, vorrei risolvere un piccolo dubbio.
Un albero binario ha tra le proprietà la caratteristica che può essere vuoto. Un albero "normale" no.
vorrei sapere se un solo nodo può essere un albero.
Ciao a tutti, vorrei risolvere un piccolo dubbio.
Un albero binario ha tra le proprietà la caratteristica che può essere vuoto. Un albero "normale" no.
vorrei sapere se un solo nodo può essere un albero.
-Montanelli-: Ma lei evadeva quasi sempre, no?
-Mesina-: Sì, ho la fortuna di avere i polsi più grossi delle mani...
ehm, il fatto che sia un albero binario implica che prima di tutto sia un albero
cmq sì, basta un solo nodo per avere un albero
23-08-2005: Udinese in cémpions lìg
Questa estate l'ho passata a Tallin
grazie.
Cmq io sapevo, per il fatto che può avere 0 nodi, che un albero binario è un "oggetto" diverso da un albero
-Montanelli-: Ma lei evadeva quasi sempre, no?
-Mesina-: Sì, ho la fortuna di avere i polsi più grossi delle mani...
Io non ho mai sentito dire che un albero (qualsiasi) non possa avere 0 nodi. In fin dei conti un albero è un grafo connesso, non orientato ed aciclico: un insieme di 0 nodi è un albero vuoto.
Un albero binario è UN ALBERO in cui ogni nodo può avere al massimo 2 figli, ossia ne può avere 0, 1 oppure 2. Ma rimane, comunque, un albero.
Possiamo vederla da un punto di vista della programmazione, secondo il paradigma Object Oriented, in questo modo:
Ciao.codice:public class Albero { ... } public class AlberoBinario extends Albero { ... }
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
un'ultima domanda.
un albero binario di altezza k e n nodi è definito pieno se contiene (2^k)-1 nodi.
un albero binario di altezza k e n nodi è definito completo se i suoi nodi corrispondono ai nodi da 1 a n dell'albero pieno.
questo vuol dire ke un albero pieno è sempre un albero completo?
un albero di altezza (k-1) e n nodi corrispondenti ai nodi da 1 a n di un albero pieno di altezza k è un albero completo? (o c'è il vincolo della stessa altezza?)
-Montanelli-: Ma lei evadeva quasi sempre, no?
-Mesina-: Sì, ho la fortuna di avere i polsi più grossi delle mani...
Anche a me abveva lasciato sconcertato a suo tempo ma a quanto pare è proprio così:un albero "normale"Io non ho mai sentito dire che un albero (qualsiasi) non possa avere 0 nodi. In fin dei conti un albero è un grafo connesso, non orientato ed aciclico: un insieme di 0 nodi è un albero vuoto.
non può essere vuoto,deve avere almeno un nodo.Ti cito testualmente la definizione tratta da un libro di algoritmi e strutture dati:
Definizione:Un albero è un insieme finito di uno o più nodi dove:
1-Esiste un nodo speciale chiamato root
2-i ndi restanti sono suddivisi in n (>=0)insiemi disgiunti T1,..,Tn,dove ciascuno di questi insiemi è una struttura ad albero.T1,...,Tn sono detti sottoalberi del nodo radice.
Il centro dell'attenzione non è sempre un buon posto in cui trovarsi
Mai discutere con uno stupido, la gente potrebbe non capire la differenza. (O. W.)
Io credo che si tratti semplicemente di definizioni e di ambiti di definizione. In combinatoria un grafo è una coppia di insiemi (V, E), e come tale V (l'inseieme dei nodi) puo essere vuoto.
Un albero è un grafo, per cui puo essere vuoto.
La nozione di albero binario è utilizzata soprattutto in informatica, e se includere o no l'albero vuoto è una questione di scelta. Puoi ad esempio odefinire un albero binario come un albero con un nodo radice, e ogni nodo ha un figlio destro e un figlio sinistro che sono a loro volta alberi. Questa definiziopne implica che l'albero vuoto è un albero, perche le foglie hanno come sottolaberi degli alberi vuoti.
Un definizione alternativa dice invece che un albero o è una foglia, oppure ha un nodo radice, con due figli destro e sinistro che sono alberi a loro volta. In questo caso l'albero vuoto non rientra nella definzione.
Secondo me è una questione di scelta, e in base alle applicazioni si puo scegliere l'una o latra definizione. Cosi come in alcuni testi di algebra lo '0' fa parte dei numeri naturali, mentre in altre definizioni no. Ovviamente se stai studiando su un testo puoi seguire la sua definizione in modo da non avere problemi nelle dimostrazioni.
Sun Certified Java Programmer
EUCIP Core Level Certified
European Certification of Informatics Professionals
Infatti... anche in questo caso, come altre in matematica / analisi, si accettano o meno delle definizioni in base al caso specifico e all'ambito in cui vengono utilizzate.
Ne è un bell'esempio la serie di Fibonacci (era stato aperto un thread alcuni mesi fa in proposito):
alcune definizioni dicono che F(0) = 1, altre dicono che F(0) = 0. Tutto stà nel mettersi d'accordo prima!
Ciao.
"Perchè spendere anche solo 5 dollari per un S.O., quando posso averne uno gratis e spendere quei 5 dollari per 5 bottiglie di birra?" [Jon "maddog" Hall]
Fatti non foste a viver come bruti, ma per seguir virtute e canoscenza
Si sono d'accordo,del resto un libro non è la bibbia!Secondo me è una questione di scelta, e in base alle applicazioni si puo scegliere l'una o latra definizione. Cosi come in alcuni testi di algebra lo '0' fa parte dei numeri naturali, mentre in altre definizioni no. Ovviamente se stai studiando su un testo puoi seguire la sua definizione in modo da non avere problemi nelle dimostrazioni.
Il centro dell'attenzione non è sempre un buon posto in cui trovarsi
Mai discutere con uno stupido, la gente potrebbe non capire la differenza. (O. W.)