[C] Come ri riempie un albero di questo tipo?

[leadergl]

Raga come si riempie una struttura di questo tipo?

struct TipoAlbero
{
	char elemento;
	struct TipoAlbero *figlio;
	struct TipoAlbero *fratello;
};

Questa è la relativa immagine:

[andbin]

Sei ancora impegnato con la Tassonomia?

[leadergl]

no, il "progetto" l'ho consegnato...ma mi sono accorto che dopo aver fatto, con mille fatiche, funzionare tutto ho sbagliato a far costruire l'albero......

e quindi mo so diventato curioso e vorrei sapere come si riempie normalmente un albero di questo tipo...

chi mi aiuta?

[leadergl]

...up...

[anx721]

e' un albero n-rio; qual è il tuo problema di preciso?

[leadergl]

riempirlo secondo uno schema...nel senso prima il nodo poi gli eventuali figli per poi passare pian piano ai vari eventuali fratelli....

quindi, prendendo ad esempio il disegno che ho postato, seguendo questo ordine:

[Ufo13]

non ho capito bene cosa vuoi dire.... Lo riempi come vuoi basta che in fase di lettura segui lo stesso schema altrimenti sballi l'ordine

[Ufo13]

comunque non mi sembra una struttura molto astuta... Il nodo radice ha 1 solo figlio e nessun fratello?

[anx721]

Originariamente inviato da Ufo13

comunque non mi sembra una struttura molto astuta... Il nodo radice ha 1 solo figlio e nessun fratello?

proprio perchè è laradice non ha fratelli...è una rapprsentazione abbastanza standard per gli alberi n-ari

[leadergl]

Originariamente inviato da anx721

proprio perchè è laradice non ha fratelli...è una rapprsentazione abbastanza standard per gli alberi n-ari

si infatti...credo sia la rappresentazione più normale possibile di un albero di questo tipo...

cmq il mio quesito era un altro...qualcuno può aiutarmi?

[leadergl]

dai raga....help...

[crick_pitomba]

ciao,
non ho capito la domanda. cioè
da come hai rappresentato la figura sembra un albero strano
ma in effetti è un semplice albero binario in cui ogni nodo ha due rami.

per riempire questa struttura devi definire tu un algoritmo sulla base del quale decidi quando prendere il ramo a sinistra e quando prendere il ramo a destra

se vuoi riempire l'albero ricreando proprio quella figura, puoi utilizzare un algoritmo di riempimento basato sui confronti in cui se ad esempio il valore da inserire è minore del valore del nodo vai a sinistra (figlio), se il valore del nodo è maggiore della radice, vai a destra(fratello).

una possibile soluzione ad esempio è (ho messo dei numeri, per comodità)

immetti per primo il valore in cella 1, poi quello in cella 2 ecc

[leadergl]

si però io non ho mai detto che il mio è un albero ordinato...

il mio problema è diverso, devo costruire un Albero di Tassonomie, il tutto è spiegato in un altro thread, questo: http://www.hwupgrade.it/forum/showpo...6&postcount=17

cmq in generale se io volessi riempire l'albero così:

radice
      figlio_1
      figlio_2
            figlio_1 (di figlio_2)
            figlio_2 (di figlio_2)
                  figlio_1 (di figlio_2 di figlio_2)
            figlio_3 (di figlio_2)
      figlio_3
      figlio_4
      figlio_5
            figlio_1 (di figlio_5)
            figlio_2 (di figlio_5)

come si farebbe?

[crick_pitomba]

ho letto un po' l'altro thread e ho cercato di capire cosa ti potesse servire ma mi manca un piccolo dettaglio: non hai mai specificato come i figli sono legati ai genitori.Questo è alla base dell'algoritmo di costruzione dell'albero.

Comunque, se non ho capito male, tu hai la struttura dell'albero stampata sul file e leggendo una riga alla volta voui ricostruire l'albero?

sei già in grado di capire leggendo il file a che livello dell'albero sei?

cioà leggendo la sesta riga di

radice
      figlio_1
      figlio_2
            figlio_1 (di figlio_2)
            figlio_2 (di figlio_2)
                  figlio_1 (di figlio_2 di figlio_2)
            figlio_3 (di figlio_2)
      figlio_3
      figlio_4
      figlio_5
            figlio_1 (di figlio_5)
            figlio_2 (di figlio_5)

sai che sei al terzo livello di figli?
e leggendo poi la settima riga sai che sei risalito di un livello?


P.S. ho provato a contattarti via msn

[beppegrillo]

La struttura del file è questa, il file devi scorrerlo dall'alto verso il basso, in base al valore (n_filgli) sai se ti trovi su un livello oppure sei sceso a livello+1.
La struttura dati che puoi usare è quella del figlio_sx, fratello_dx, ma non è detto che tu debba distinguerli, visto che non ha nessuna importanta, quindi un nodo avrà una lista concatenata di n figli.

Struct nodo {
char* name;
struct nodo* figli
struct nodo* next
char** proprieta (tassonomia)
}

n_figli radice
     n_figli figlio_1
      " figlio_2
           " figlio_1 (di figlio_2)
           " figlio_2 (di figlio_2)
                  figlio_1 (di figlio_2 di figlio_2)
            figlio_3 (di figlio_2)
      figlio_3
      figlio_4
      figlio_5
            figlio_1 (di figlio_5)
            figlio_2 (di figlio_5)

[Qu@ker]

Non mi e' ancora chiaro com'e' il file dei dati.
Perche' non ne posti un pezzetto, giusto per capire cosa si deve leggere?
Il resto non mi pare difficile, per esempio:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct albero {
	char nome[5];
	struct albero *fratello;
	struct albero *figlio;
} alberoStrano;

typedef struct famiglia {
	char *nome;
	int figli;
} famiglia;

famiglia dati[] = { 
	{"1", 5}, {"11",0}, {"12",3}, {"121",0}, {"122",1}, 
	{"1221",0}, {"123",0}, {"13",0}, {"14",0},{"15",2},
	{"151",0},{"152",0},{NULL,0}
};

int indice;

void leggiNodo(famiglia *dati, alberoStrano **nodo, int fratelli)
{
	int figli;

	if (dati[indice].nome == NULL)
		return;

	*nodo = malloc(sizeof(alberoStrano));
	strcpy((*nodo)->nome, dati[indice].nome);
	figli = dati[indice++].figli;

	if (figli > 0) {
		leggiNodo(dati, &((*nodo)->figlio), figli-1);
	} else
		(*nodo)->figlio = NULL;

	if (fratelli > 0)
		leggiNodo(dati, &((*nodo)->fratello), fratelli-1);
	else
		(*nodo)->fratello = NULL;
}

void stampaNodo(alberoStrano *nodo)
{
	printf("%s", nodo->nome);

	if (nodo->figlio) {
		printf(" (");
		stampaNodo(nodo->figlio);
		putchar(')');
	}

	if (nodo->fratello) {
		putchar(' ');
		stampaNodo(nodo->fratello);
	}
}

int main()
{
	alberoStrano *radice;

	indice = 0;
	leggiNodo(dati, &radice, 0);
	stampaNodo(radice);
	putchar('\n');
        /* qui si dovrebbero liberare le risorse allocate,
            ma lo lascio come esercizio ;) */

	return 0;
}

[beppegrillo]

Originariamente inviato da Qu@ker

Non mi e' ancora chiaro com'e' il file dei dati.
Perche' non ne posti un pezzetto, giusto per capire cosa si deve leggere?
Il resto non mi pare difficile, per esempio:

In allegato c'è il testo.

P.s Ma perchè un albero n-ario è strano?

[Qu@ker]

Originariamente inviato da beppegrillo

In allegato c'è il testo.

E' un file di Word. Ho provato ad aprirlo con OpenOffice, ma dove dice
"ad esempio:", ci sono solo alcune righe vuote.

Originariamente inviato da beppegrillo

P.s Ma perchè un albero n-ario è strano?

Be' quello non e' un albero n-ario, che sarebbe un albero dove ogni nodo
ha esattamente n figli.
E' un albero ordinato, che puo' essere visto come un albero binario organizzato
in modo particolare (da qui lo strano).

[beppegrillo]

Originariamente inviato da Qu@ker

Be' quello non e' un albero n-ario, che sarebbe un albero dove ogni nodo
ha esattamente n figli.
E' un albero ordinato, che puo' essere visto come un albero binario organizzato
in modo particolare (da qui lo strano).

Non è un albero ordinato, ol nemmeno n-ario, poichè i figli sono variabili.
Comunque era un rtf, l'ho rinominato.

[Qu@ker]

Originariamente inviato da beppegrillo

Non è un albero ordinato, ol nemmeno n-ario, poichè i figli sono variabili.

Secondo Sedgewick, quello e' un albero ordinato.
Comunque ...basta capirsi.

Originariamente inviato da beppegrillo

Comunque era un rtf, l'ho rinominato.

Ok, l'ho rinominato, ma continuo a non vedere l'esempio...
Pero', da quello che leggo, il secondo quesito richiede la costruzione del
TFILE, quindi sei TU che mi devi dire come e' fatto...