PDA

Visualizza la versione completa : [?] distinzione albero da albero binario


graziano mesina
13-09-2004, 11:10
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
13-09-2004, 11:14
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
13-09-2004, 11:19
grazie.
Cmq io sapevo, per il fatto che pu avere 0 nodi, che un albero binario un "oggetto" diverso da un albero

LeleFT
13-09-2004, 13:46
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. :ciauz:

graziano mesina
13-09-2004, 13:48
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
14-09-2004, 13:37
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
14-09-2004, 14:44
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.

:ciauz:

LeleFT
14-09-2004, 15:00
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. :ciauz:

unomichisiada
14-09-2004, 20:15
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!

Loading