[?] distinzione albero da albero binario

[graziano mesina]

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.

[pippo75]

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

[graziano mesina]

grazie.
Cmq io sapevo, per il fatto che può avere 0 nodi, che un albero binario è un "oggetto" diverso da un albero

[LeleFT]

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:

public class Albero {
   ...
}

public class AlberoBinario extends Albero {
   ...
}

Ciao.

[graziano mesina]

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

[unomichisiada]

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.

Anche a me abveva lasciato sconcertato a suo tempo ma a quanto pare è proprio così:un albero "normale"
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.

[anx721]

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.

[LeleFT]

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.

[unomichisiada]

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.

Si sono d'accordo,del resto un libro non è la bibbia!