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]

Originariamente inviato da 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;

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]

Originariamente inviato da 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!

Ho modificato il codice precedente e ho aggiunto i commenti.

[misterx]

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

Immagine.gif

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

[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]

Originariamente inviato da 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.

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]

Originariamente inviato da stdecden

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...