Alberi in C

[misterx]

struct inttree {
int dato;
struct inttree *left, *right;
};

typedef struct inttree inttree;


inttree *root = NULL;


// aggiungo un dato alla radice 1° livello
root = malloc(sizeof(inttree));
root->dato = 5;

// aggiungo un dato al ramo sx 2° livello
root->left = malloc(sizeof(inttree));
root->left->dato = 7;

// aggiungo un dato al ramo dx 2° livello
root->right = malloc(sizeof(inttree));
root->right->dato = 9;

// aggiungo un dato al sottoramo sx/sx e dx/sx e dx/dx del 3° livello
root->left->left = root->right->left = root->right->right = NULL;

// aggiungo un dato al sottoramo sx/dx del 3° livello
root->left->right = malloc(sizeof(inttree));
root->left->right->dato = 11;

// aggiungo un dato al sottoramo sx/dx/sx e sx/dx/dx del 4° livello
root->left->right->left = root->left->right->right = NULL;


l'esempio proposto serve solo a far comprendere come si allocano ed aggiungono dati ad un albero creando quindi nodi e conseguenti ramificazioni e sino a qui, tutto bene.
Siccome non credo che il sistema proposto sia efficacissimo, mi chiedevo come ci si posiziona su un determinato nodo di un albero e quindi, se il nodo non dovesse esistere, lo si crea.

Vi prego, solo per chiarezza, di evitare di postare codice chilometrico che genererebbe solo ulteriore confusione; mi interessa capire il meccanismo e non avere il codice migliore per posizionarsi all'iesimo nodo, non prendetela come una pretesa ma una preghiera :)

[nico88desmo]

Questa funzione serve per caricare il dato a seconda se si sceglie "s - S" per inserire il dato (nel mio caso è un char) a sinistra o "d - D" a destra del nodo padre;
Alla funzione gli devi passare l'indirizzo della nodo-radice dell'albero e il dato.

Questo è il codice


void genera (s_albero **rad, char c) {

char sc;
s_albero *new;
s_albero *app;
s_albero *prec;
int libero;

libero = 0;

new = (s_albero *) malloc (sizeof(s_albero));
new->sx = NULL;
new->dx = NULL;
new->lettera = c;

if ((*rad)==NULL) {

*rad = new;

} else {

app = *rad;
while (libero==0) {
do {
printf("sx o dx di %c ? : ",app->lettera);
scanf("%c",&sc);
scanf("%c",&invio);
} while ((sc!='s') && (sc!='S') && (sc!='d') && (sc!='D'));

prec = app;
if ((sc=='s') || (sc=='S')) {
app=app->sx;
} else {
app=app->dx;
}

if (app==NULL) {
libero=1;
if ((sc=='s') || (sc=='S')) {
prec->sx = new;
} else {
prec->dx = new;
}
}
} // end while
} // end if
} // end genera

[misterx]

non riuscivi a lavorare sul mio esempio ?
Che poi tutto sommato si riduce a questo:


struct inttree {
int dato;
struct inttree *left, *right;
};

typedef struct inttree inttree;

inttree *root = NULL;

[nico88desmo]

non riuscivi a lavorare sul mio esempio ?
Che poi tutto sommato si riduce a questo:


struct inttree {
int dato;
struct inttree *left, *right;
};

typedef struct inttree inttree;

inttree *root = NULL;



Ecco il codice adattato alla tua struttura


void genera (inttree **root, int c) { // funzione chiamata per generare l'albero; viene inserito un nodo alla volta

char sc, invio;
inttree *new;
inttree *app;
inttree *prec;
int libero;

libero = 0;

new = (inttree *) malloc (sizeof(inttree)); // creo il nuovo nodo
new->left = NULL; // puntatore di SX a null
new->right = NULL; // puntatore di DX a null
new->dato = c; // inserisco dato nel nodo

if ((*root)==NULL) { // se la radice è vuota

*root = new; // posiziono il nodo creato come radice

} else {

app = *root; // memorizzo in una variabile d'appoggio la radice
while (libero==0) { // libero; se 1 --> inserisco il nodo creato nell'albero; se 0 --> scorro l'albero
do {
printf("sx o dx di %d ? : ",app->dato); // l'utente decide se inserire a SX o a DX del nodo padre
scanf("%c",&sc);
scanf("%c",&invio);
} while ((sc!='s') && (sc!='S') && (sc!='d') && (sc!='D'));

prec = app; // memorizzo il nodo app (prec poi diventa il padre di app)
if ((sc=='s') || (sc=='S')) { // se l'utente ha scelto a SX
app=app->left; // appoggio si posiziona nel nodo figlio SX
} else { // altrimenti
app=app->right; // appoggio si posiziona nel nodo figlio DX
}

if (app==NULL) { // se appoggio è NULL
libero=1; // libero = 1 --> inserisco il nodo creato all'inizio nell'albero
if ((sc=='s') || (sc=='S')) {
prec->left = new; // se ho scelto a SX inserisco a SX
} else {
prec->right = new; // altrimenti a DX
}
}
} // end while
} // end if
} // end genera

[misterx]

scusa, ma senza un briciolo di commento non riesco a capire come lavora il tuo algoritmo!
Il codice di inserimento di un nuovo nodo è mescolato con quello dell'input dei dati, boh!

[nico88desmo]

scusa, ma senza un briciolo di commento non riesco a capire come lavora il tuo algoritmo!
Il codice di inserimento di un nuovo nodo è mescolato con quello dell'input dei dati, boh!

Ho modificato il codice precedente e ho aggiunto i commenti.

[misterx]

un pò di pazienza che non è un argomento poi così banale

51642

a mano a mano che alloco nodi la configurazione (struttura) che si viene a creare è come quella nel mio disegno ?

[nico88desmo]

La struttura è tipo questa

http://www.pctuner.info/up/results/_200707/20070724164646_albero_binario.gif

[misterx]

lo so che è rappresentato così un albero binario. Mi interessava sapere se strutturalmente nella memoria del calcolatore si hanno aree di memoria configurate come nel mio schema e collegate come nel mio schema.

[nico88desmo]

lo so che è rappresentato così un albero binario. Mi interessava sapere se strutturalmente nella memoria del calcolatore si hanno aree di memoria configurate come nel mio schema e collegate come nel mio schema.

Si si, è come nel tuo schema.

[gepeppe]

salve, usando il "cerca" ho trovato questa interessante discussione. Avrei una domanda a riguardo...ma se invece di voler creare un albero binario, io volessi creare un albero con k figli?? cioè, ho una radice, poi ogni nodo può avere da 0 a k figli, e cosi via....

[stdecden]

Un nodo dell'albero dovrebbe contenere:
- Una lista di nodi


struct Node
{
std::list<*Node> Nodi;
};

(Codice non testato)

[gepeppe]

Un nodo dell'albero dovrebbe contenere:
- Una lista di nodi


struct Node
{
std::list<*Node> Nodi;
};

(Codice non testato)

è una struttura nodo con all'interno???? non capisco di che tipo di membro si tratta...