Newsgroup: it.comp.lang.c
Titolo: Delucidazioni su alberi binari

Salve a tutti e grazie delle risposte...
Ho tentato di scrivere un programmino che prendesse in input una sequenza
di numeri in un ciclo infinito che termina allorche' inserisco 0...
Ogni numero che inserivo volevo fosse posto nel giusto ordine nell'albero
binario e allorche' inserivo 0, volevo che la funzione inorder mi stampasse
la sequenza dei numeri inseriti ordinata in ordine crescente...
Comunque il programma e' il seguente:
=========================================================================
#include <stdio.h>
#include <stdlib.h>
struct intree
{
        int dato;
        struct intree *left, *right;
};
typedef struct intree inttree;
void inorder(inttree *root)
{
        if(root!=NULL)
                {
                        inorder(root->left);
                        printf(" \n Numero: %d",root->dato);
                        inorder(root->right);
                }
}
void TreeInsert(inttree *root,inttree *z)
{
        inttree *y,*x;
        y=NULL;
        x=root;
        while(x!=NULL)
                {
                        y=x;
                        if(z->dato<x->dato)
                                x=x->left;
                        else
                                x=x->right;
                }
        z=y;
        if(y==NULL)
                root=z;
        if(z->dato<y->dato)
                y->left=z;
        else
                y->right=z;
}
inttree* newnode()
{
        return(malloc(sizeof(inttree)));
}
main()
{
        int k;
        inttree *root=NULL, *z=NULL;
        while(1)
        {
                printf("\nInserisci un numero(0 per terminare): ");
                scanf("%d",&k);
                if(k==0)
                {
                printf("\n-----------------INORDER--------------------\n");
                inorder(root);
                printf("\n");
                exit(1);
                }
                z=newnode();
                z->dato=k;
                z->left=NULL;
                z->right=NULL;
                printf("\nZ vale: %d\n",z->dato);
                if(root==NULL)
                        {
                                root=newnode();
                                root->dato=k;
                                root->left=NULL;
                                root->right=NULL;
                        }
                else
                        TreeInsert(root,z);
                free(z);
        }
}
============================================================================
===
Il programma si blocca se inserisco per esempio 543 654 765 (e penso sia
giusto, poiche' il nodo sinistro deve essere minore della radice) ma anche
inserendo sequenze corrette dopo un po' inspiegabilmente si blocca...
Se inserisco per esempio 67 78 32 e poi 0, la procedura inorder mi stampa
67 in un loop infinito...
Sicuramente penso che l'errore sia in TreeInsert: faccio presente che l'ho
ricopiata da un libro prestatomi(era scritta in metalinguaggio e percio'
l'ho riadattata)... La funzione inorder dovrebbe essere giusta...
Tuttavia non sono riuscito a capire cosa non vada: da quel (pochissimo) che
ho capito la TreeInsert confronta il valore del nodo z coi valori di root
via via discendendo nell'albero, a destra o a sinistra a seconda dei
risultati dei confronti...
Dov'e' l'errore?
Scusate se stresso su sto argomento, ma vorrei capire dove sbaglio...
Grazie ancore per le risposte...
Steve

Il tuo programma entra in un loop infinito perche' la funzione 
TreeInsert fa un gran casino....!!!
Quando si inseriscono in sequenza i seguenti valori es. 7,8,9 la 
TreeInsert causa un loop al terzo numero.Cio' accade perche' il 
puntatore right del nodo radice dopo la chiamata TreeInsert per il 
numero 8 puntera' a se stesso cioe' al nodo radice stesso....!!!!!! 
Quindi nella terza chiamata della medesima funzione cioe' per il valore 
9, il ciclo while(x!=NULL) della funzione sara' sempre vera perche' 
quando l'else eseguira' l'istruzione x=x->right; x puntera' sempre a 
root in quanto e' stato fatto puntare a root nella chiamata a funzione 
del TreeInsert per il numero 8.
 
Ma non finisce qui....... il tuo codice inoltre non funziona perche' 
l'istruzione free(z) non fa altro che cancellare la locazione di memoria 
del nodo appena inserito nell'albero (es.uno dei puntatori della root 
 [left o right] puntera' ad un nodo che verra' cancellato da 
free(z)....!!!!!
FAI MOLTA ATTENZIONE  QUANDO USI I PUNTATORI...!!!!
La funzione TreeInsert l'ho riscritta in modo da renderla corretta (la 
funzione non controlla se l'albero e' NULL in quanto cio' non potra' mai 
accadere perche' il main chiamera' la funzione TreeInsert solo quando 
l'albero ha gia' un nodo ROOT) e non accetta valori gia' esistenti
 
Non devi fare altro che sostituirla alla tua...!!!
Ah!!  NON DIMENTICARE DI CANCELLARE L'ISTRUZIONE free(z); SITUATA DOPO 
LA FUNZIONE TreeInsert(root,z);
Un salutone da Luciano !!! :-))
void TreeInsert(inttree *root,inttree *z)
{
   inttree *tmp;
     tmp=root;
      while(true){
         if(z->dato < tmp->dato){
            if(tmp->left==NULL){
               tmp->left=z;
               return;
            }else tmp=tmp->left;
         }else if(z->dato > tmp->dato){
            if(tmp->right==NULL){
               tmp->right=z;
               return;
            }else tmp=tmp->right;
         }else if(z->dato==tmp->dato){
            printf("\nErrore Valore: %d\nGia' 
Esistente...!!!\n\n",tmp->dato);
            return;
         }
      }
}
By Luciano!
