Newsgroup: it.comp.lang.c
Titolo: Alberi binari: HELP!

Salve a tutti, ho appena iniziato a studiare gli alberi binari di ricerca e
già mi trovo in difficoltà...
Praticamente ho una struttura albero di questo tipo
struct albero
{
    int dato;
    struct albero *left;
    struct albero *right;
}
typedef struct albero albero;
Ora se volessi creare un nodo potrei fare così:
main()
{
    albero *prova;
    prova=malloc(sizeof(albero));
    if(prova==NULL)
            .........
    prova->dato=12;
    prova->left=NULL;
    prova->right=NULL;
......
}
Questo modo di operare tuttavia come facilmente si capisce, non è affatto
elegante e per alberi di 100 elementi o + improponibile...(per alberi di +
di 5 elementi!)....
Qualcuno non potrebbe farmi un esempio basandomi su ciò che ho detto sopra
 di come si faccia a creare l'albero e a inserire un nodo che rispetti le
proprietà dell'albero? Quello che mi serve, in pratica sono due
primitive.... Il libro che ho dedica due o tre pagine all'argomento ma da
moltissime cose per scontato!
Aiutatemi vi prego, sono disperato!
Anche perchè capito questo, mi manca solo il gestire la cancellazione e poi
è fatta!
In alternativa non è che mi potreste indicare un url dove l'argomento venga
trattato in modo lineare in un linguaggio non troppo arcano?
Grazie mille...
Stefano

 ha scritto nel messaggio
news:a0ir6k$ep7$1...@nreadb.inwind.it...

ti servono due funzioni :
albero* puntatore_a_nuovo_nodo = insert_left(albero* nodo_a_cui_appendere,
int nuovo_dato);
albero* puntatore_a_nuovo_nodo = insert_right(albero* nodo_a_cui_appendere,
int nuovo_dato);
il cui corpo è circa:
{
     albero*  nuovo=malloc(sizeof(albero));
     if(prova==NULL)
             .........
     nuovo->dato=nuovo_dato;
     nuovo->left=NULL;
     nuovo->right=NULL;
     nodo_a_cui_appendere->left=nuovo;  (o right nell' altro caso)
     return nuovo;
}
per cancellare :  void delete_node(albero* nodo_da_cancellare);
il cui corpo è circa:
{
    if (nodo_da_cancellare->left /* != NULL*/)
delete_node(nodo_da_cancellare->left );   (ricorsiva, discende il ramo
sinistro)
    if (nodo_da_cancellare->right/* != NULL*/)
delete_node(nodo_da_cancellare->right);  (ricorsiva, discende il ramo
destro)
    free(nodo_da_cancellare); (libera memoria del nodo corrente)
}
----
Sergio Bianchi

source: corso di Laboratorio di Algoritmi e Strutture Dati.
Questi pezzi di codice ti forniscono una base per crearti un'ADT
albero binario, senza troppe pretese, ma funzionante.
http://www.mfn.unipmn.it/~vincenzo/LAB-ASD/ADT/generic-def.txt
http://www.mfn.unipmn.it/~vincenzo/LAB-ASD/ADT/binary-tree.txt
Ci sono alcuni difetti:
1) manca una sorta di namespace (una cosa rudimentale, del tipo 
   btree_nome_funzione() giusto per poter distinguere tra funzioni 
   simili dovessi operare sia su alberi che su liste)
2) mancano alcuni mattoncini:
   - una macro per capire se il nodo in questione e' una foglia
3) l'idea di avere una funzione init che inizializza l'albero e lo 
   crea non e' bella; dovresti spezzare in 2 funzioni: la 
   btree_create() che all'ca la struttura dati albero e la iniz che lo
   inizializza correttamente a NULL, oppure se ne preferisci una sola 
   rinominala create()
4) le funzioni di visita cosi' create non sono adatte ad algoritmi 
   come quello per calcolare i codici di Huffman: in casi del genere 
   devi scorrere "manualmente" l'albero con le macro LEFT() e RIGHT().
Comunque ti fornisce gia' un'idea di partenza.
Quando capisci questo codice passa a guardare gli header file e la
documentazione della Glib (
www.gtk.org
)... si implementano l'albero
generico in modo veramente carino :)
Mox :)

Ho scritto del codice che ti potrebbe essere utile.
La funzione CreaNodo alloca ed inizializza un nodo al valore specificato.
La funzione Insert inserisce un nodo nell' albero.
Ah! il codice e' scritto per S.O. dos-Windows ma con qualche modifica 
potrebbe andare anche per linux !!!
Bye bye da Luciano !!!   :-))
#include <stdio.h>
#include <stdlib.h>
struct Nodo {
   int data;
   struct Nodo *left;
   struct Nodo *right;
};
typedef struct Nodo * Albero;
Nodo *CreaNodo(int data);
int Insert(Albero *tree,Nodo *nd);
main () {
Albero tree=NULL;
Nodo *nd=CreaNodo(25);
Nodo *nd2=CreaNodo(10),*nd3=CreaNodo(50);
   Insert(&tree,nd);
   Insert(&tree,nd2);
   Insert(&tree,nd3);
   printf("\nRoot: %d\n",tree->data);
   printf("Left: %d\n",tree->left->data);
   printf("Right: %d\n",tree->right->data);
   system("pause");
}
Nodo *CreaNodo(int data)
{
   Nodo *nd;
   nd=(Nodo *)malloc(sizeof(Nodo));
   nd->data=data;
   nd->left=nd->right=NULL;
   return nd;
}
int Insert(Albero *tree,Nodo *nodo)
{
   Albero tmp;
   if(*tree==NULL){
      *tree=nodo;
      return 0;
   }else {
      tmp=*tree;
      while(true){
         if(nodo->data < tmp->data){
            if(tmp->left==NULL){
               tmp->left=nodo;
               return 0;
            }else tmp=tmp->left;
         }else if(nodo->data > tmp->data){
            if(tmp->right==NULL){
               tmp->right=nodo;
               return 0;
            }else tmp=tmp->right;
         }else if(nodo->data==tmp->data){
            printf("\nErrore Valore: %d\nGia' 
Esistente...!!!\n\n",tmp->data);
            return -1;
         }
      }
   }
}
by luciano
