Newsgroup: it.comp.lang.c
Titolo: ALBERI BINARI HELP!!!

ciao a tutti,
da un po di tempo a questa parte cerco di implementare dei programmi con
strutture di alberi binari di ricerca.
Il programma è molto semplice in quanto si tratta si inserire dei valori (3
in questo caso) in un albero binario di ricerca e alla fine stampare su
video l'albero ordinato.
Ma all'avvio del programma sistematicamente ricevo lo sgradevole messaggio:
segmentatio faul.
C'è qualche anima di buon cuore che potrebbe dare un'occhiata al mio
codice??
Grazie in anticipo
Ciao,
Luca
#include <stdio.h>
#include <stdlib.h>
typedef struct nodo
    {
    int key;
    struct  nodo  *left,  *right;
    }NODO;
/* prototipi */
void insert(NODO  **ptr, int g);
void stampalbero(NODO *ptr);
main()
{
/* dichiarazioni */
int x, i=0;
NODO *tree;
printf("inserisci 3 valori: \n");
while( i<3)
   {
    scanf("%d",  &x);
    insert(&tree,   x);
    i++;
    }
stampalbero(tree);
}
void insert(NODO **ptr,  int  g)
{
/* la radice esiste */
if(*ptr)
    insert(&((*ptr)->key > g? (*ptr) ->right: (*ptr)->left), g);
else
/* la radice non esiste,  viene creata l'albero*/
    {
    *ptr=(NODO *)malloc(sizeof(NODO));
    (*ptr)->key=g;
    (*ptr)->left=(*ptr)->right=NULL;
    }
}
void stampalbero(NODO *ptr)
{
/* caso albero vuoto */
if(ptr ==NULL)
   {
    printf("albero vuoto");
    return;
    }
/* caso albero composto da sola radice */
if(ptr->left==NULL  &&  ptr->right==NULL)
    printf("%d",  ptr->key);
else
    {
    /* stampa dell'albero ordinato */
    stampalbero(ptr->left);
    printf("%d",   ptr->key);
    stampalbero(ptr->right);
    }
}

Grazie in anticipo
Mai farlo ;-)
Alex
P.S. fammi sapere se sono riuscito a risolvere tutti i problemi o meno.

codice??
No, ma sono ben disposto a riscriverlo da zero.
#include <stdio.h>
#include <stdlib.h>
typedef struct nodo_tag {
               int value ;
               struct nodo_tag *left, *right ;
        } *pnodo ;
void insert( pnodo* root, int v )
{
     if ( !*root )
     {
        *root = malloc( sizeof **root ) ;
        (*root)->left = (*root)->right = NULL ;
        (*root)->value = v ;
     }
     else
     if ( v <= (*root)->value )
        insert( &(*root)->left, v ) ;
     else
        insert( &(*root)->right, v ) ;
}
void write( pnodo root )
{
     if ( root )
     {
        write( root->left ) ;
        printf( "%d\n", root->value ) ;
        write( root->right ) ;
     }
}
void freetree( pnodo root )
{
     if ( root )
     {
        freetree( root->left ) ;
        freetree( root->right ) ;
        free( root ) ;
     }
}
int main()
{
    pnodo root = NULL ;
    insert( &root, 4 ) ;
    insert( &root, 3 ) ;
    insert( &root, 2 ) ;
    insert( &root, 1 ) ;
    insert( &root, 7 ) ;
    insert( &root, 6 ) ;
    insert( &root, 5 ) ;
    write( root ) ;
    freetree( root ) ;
    return 0 ;
}

implementarla in modo iterativo e non ricorsivo.
Falso, ma tu sei un genio e mi saprai spiegare il perche'.

 Falso, ma tu sei un genio e mi saprai spiegare il perche'.
No, vorrei che me lo "spiegassi" tu, visto che io continuo a rimanere della
mia idea !
Alex

mia idea !
Se affermi che qualcosa e' meglio di qualcos'altro devi anche
spiegarne il perche'.  Se mi spieghi le tue ragioni, saro' lieto
di smentirti.

 No, ma sono ben disposto a riscriverlo da zero.
Se prima di uscire dal tuo programma (subito prima di return 0;) scrivo
 write( root ) ; il programma da errore. Dimentichi in freetree() di
cambiare il valore di root in NULL. (e' quello che io facevo con
*ptr=NULL; nel programma di Luca da me corretto (che tuttavia avrei
implementato in modo differente)).
Quindi questo e' un errore, comune, ma sempre grave !
In sostanza devi cambiare :
void freetree( pnodo root )
{
     if ( root )
     {
        freetree( root->left ) ;
        freetree( root->right ) ;
        free( root ) ;
     }
}
con :
void freetree( pnodo* root )
{
     if ( *root )
     {
        freetree( &(*root)->left ) ;
        freetree( &(*root)->right ) ;
        free( *root ) ;
        *root=NULL;
     }
}
e cambiare la chiamata : freetree( root ) ;  in   freetree( &root ) ;
Alex
P.S. codice main() con il quale il tuo programma (non corretto da me) dava
errore:
int main()
{
    pnodo root = NULL ;
    insert( &root, 4 ) ;
    insert( &root, 3 ) ;
    insert( &root, 2 ) ;
    insert( &root, 1 ) ;
    insert( &root, 7 ) ;
    insert( &root, 6 ) ;
    insert( &root, 5 ) ;
    write( root ) ;
    freetree( root ) ;
    write( root ) ;
    return 0 ;
}

 di smentirti.
A parte il fatto che posso rigirarti la tua ultima frase: se tu dici che e'
falso cio' che dico motivalo. ...
In generale la ricorsione e' piu' lenta della iterazione (e non parlarmi di
strane ottimizzazioni). Inoltre usa molta piu' memoria.
Non mi riferisco a cio' che accade con Fibonacci, che ricorsivamente e'
molto meno efficiente in quanto calcola alcune espressioni piu' di una
volta. Mi riferisco invece al semplice fatto che, al contrario della
funzione StampaAlbero**, la funzione Inserisci puo' essere scritta
iterativamente con grande facilita'. In generale l'iterazione (che non usa
uno stack per emulare la ricorsione) e' piu' veloce ed efficiente, quindi
perche' mai non usarla ???
** La funzione StampaAlbero iterativa invece diventa troppo complicata e
poi, per comodita', usando uno stack, non ha praticamente nessun vantaggio
rispetto alla versione ricorsiva.
Concudendo, per la funizone Inserisci invece non serve nessuno stack,
nessuna chiamata ad altra funzione e tanto meno nessuna ricorsione.
Alex

nessuna chiamata ad altra funzione e tanto meno nessuna ricorsione.
Non dire idiozie, per cortesia.

Quindi questo e' un errore, comune, ma sempre grave !
Ci risiamo, nella tua arrampicata sugli specchi, ti dimentichi di
una cosa importante.  Qualsiasi operazione su un puntatore
deallocato e' "undefined behavior".
Il settaggio a NULL del puntatore, dopo la liberazione della
memoria e' superfluo, perche' il programmatore dovrebbe sapere
che la memoria non va utilizzata dopo una free (e tantomeno dopo
una serie di free come in freetree).
Evita, quindi, di fare correzioni inutili.

 Ovviamente ho adattato il tuo codice, non e' il massimo cmq.
Con la mia ultima frase intendevo dire che tutto questo e' inutile, basta
scrivere (sempre modificando il tuo codice):
void stampalbero(NODO *ptr)
{
 /* caso albero vuoto */
 if(ptr==NULL)
 {
  printf("albero vuoto ");
  return;
 }
    /* stampa dell'albero ordinato */
    if(ptr->left!=NULL)stampalbero(ptr->left);
    printf("%d ",ptr->key);
    if(ptr->right!=NULL)stampalbero(ptr->right);
}
Cerco sempre di attenermi al tuo codice come vedi. Vedi che senza i 3 casi
funziona ugualmente ? I due if prima della chiamata di stampalbero evitano
che avvenga il caso (ptr==NULL). Di conseguenza tale caso avviene solo se
viene passato un puntatore nullo (albero vuoto).
Alex

 Evita, quindi, di fare correzioni inutili.
Non e' inutile, proprio per quello che dici: "Qualsiasi operazione su un
puntatore
deallocato e' "undefined behavior"" e' bene evitare problemi settandolo su
NULL.
Ricordati che una funzione, cosi' come una classe, devono essere utilizzate
da tutti e non solo da chi le produce. Tanto piu' che anche l'autore della
funzione potrebbe sbagliarsi.
Una funzione deve anche funzionare con qualsiasi codice main(), deve essere
generale al massimo, e la tua con il main() da me postato la tua funzione
non funziona.
Non credo sia inutile il mio appunto. Credo invece sia inutile per te, visto
che hai la testa dura e non ascolti, rimani della tua idea e farai ancora
funzioni insicure.
Alex

 Non dire idiozie, per cortesia.
Ti assicuro che e' cosi', se tu non sai implementarla non e' colpa mia !
Alex

alle stesse prestazioni.
Non nel caso specifico di un albero binario. Tanto e` vero 
che il Cormen-Leiseron-Rivest (Introduction to Algorithms) 
riporta la versione algoritmica iterativa analizzandone  
la complessita. 
Lo stesso dicasi per molti libri di algoritmi, come quello del 
prof. Aho. (Data Structures and Algorithms).
In altri casi, (es. Torre di Hanoi) , e` impossibile 
risolvere problemi  in maniera iterativa in maniera efficente.
Per dovere di cronaca  la complessita` dell'Algoritmo 
presentato sul Cormen e` di O(h) dove h e` l'altezza 
dell'albero. 
--
"Everything should be as simple as possible, 
   but no simpler" - Albert Einstein
--

 valore. (non e' questo uno spreco se iterativamente basta un ciclo ?!?)
Da notare che nel programma in esame, 100 chiamate ricorsive sono una cosa
molto improbabile. Infatti se un inserimento richiede 100 chiamate ricorsive
vuol dire che l'albero se construito in modo casuale contiene circa 2^100
elementi....un pò troppi no?
Vista la struttura dell'albero binario di ricerca che di solito mantinene
un'altezza  vicina a log(n) non credo che un inserimento ricorsivo possa
essere un problema.

funzioni insicure.
ROTFL ! ma va a quel paese, impara il linguaggio e poi torna a
discutere...

 essere un problema.
Allora... e se io inserisco nell'albero binario di ricerca 100 numeri in
ordine ?!? Puo' capitare, no ?!? Inoltre...
Il fatto che tu dica che l'albero binario di ricerca mantiene l'altezza
vicino a log(n) con "numeri casuali" non e' vero. E' vero se lo bilanci, ma
se inserisci dei numeri random ne riparliamo fra poco! (per non dire, come
ho detto, se li inserisci ordinati).
A parte il fatto che avrei potuto fare l'esempio con una decina di chimate e
reggeva ugualmente: "perche' mai usare molta piu' memoria e fare 10 chiamate
di funzione ?!? "
Inoltre visto che parli di log(n) credo che tu sappia che quando si
implementa una funzione si deve sempre pensare a renderla piu' veloce anche
nei casi limite, no ?!?
MA credimi, ancora una volta, che con dei numeri random, profondita' 100 non
e' poi cosi' irraggiungibile.
Ma visto che sei uno che si interessa dell'argomento volgio darti una prova
di quello che dico:
 while(d<100){
  d=0;
  insert(&tree,rand()%32);
  c++;
 }
Questo ciclo da mettere in main cicla fino a che d non raggiunge il valore
100.
d viene azzerato ad ogni ciclo, ma viene incremento ad ogni livello di
ricorsione o ad ogni ciclo a seconda della versione.
c invece conta quanti inserimenti vengono fatti.
printf(" %d ",c); stampa quindi quanti inserimenti sono stati fatti.
Ora, con rand()%32vengono fatti 2631 inserimenti per raggiungere prfondita'
100.
Non mi dire che una persona non puo' essere interessata (e libera) di
mettere dei valori da 0 a 31.
Ok, ok, voglio darti retta, quindi proviamo rand()%150 e facciamo finta che
si voglia inserire l'eta di delle persone di un certo comune (che sono
tantissime): 9658 inserimenti. (sono meno di quante ce ne siano in molti
comuni, no ?!?)
Con rand()%1000 invece : 62974
Con rand()%10000 ?!? 410.813 (dopo di che il mio PC incomincia a fare
fatica, sigh!)
Contando che il "tuo" 2^100 e' :
+1.267.650.600.228.229.401.496.703.205.376
Beh, forse hai esagerato ! Non lamentarti del % in quanto non tutti sono
interessati a mettere valori da 0 fino a milioni di miliardi, no !?! E'
molto piu' probabile inserire valori entro un certo range. Quello che volevo
dimostrarti e' che ci sono moltissimi casi in cui h (altezza) arriva e
supera 100. Non e' "molto improbabile" come dici tu !!!
Parliamo ora di PRESTAZIONI (con rand()%10000 e profondita' 100, circa
400.000 inserimenti) tra l'isnerimento ricorsivo (di Laforgia ed il mio
iterativo):
Il programma chiamando la MIA funzione iterativa ci mette: 8 secondi crica.
Lo stesso programma chiamando quella di Laforgia ci mette: 12,5 secondi
circa.
Inoltre, anche se diventa meno elegante, se nella mia versione iterativa
metto tutte le variabili static allora arrivo a 7,5. (e' assurdo provare a
farlo con la ricorsiva di Andrea).
Sono sicuro di non aver tempo perso a spiegarti tutto questo. Sono invece
convinto di perdere tempo a spiegare le cose ad Andrea Laforgia che ora e'
convinto di sapere tutto ha chiuso nei confronti di tutti noi.
Alex

 dell'albero.
Si, questo e' ovvio.
Alex

 NULL.
Impostando il puntatore a NULL non rendi affatto il programma piů
sicuro. Semplicemente trasformi un possibile undefined behavior in un
completamente silenzioso ed altrettanto pernicioso procedere oltre.
D'altronde i programmatori C (e ancora di piů quelli C++) sono abituati
a tener conto dei puntatori invalidati.
Rendere veramente piů sicuro il programma non č affatto semplice, se si
vuole che il controllo non sia invasivo. Come minimo dovresti mettere
una assert in tutte le funzioni che utilizzano quel puntatore.
EMG

 discutere...
Ti ho dettto moltissime volte (e te lo hanno detto molti altri) di non
essere offensivo. Ancora sei nei limiti, ma molte volte sei andato oltre,
quindi ti invito a stare attento a moderare il linguaggio.
Alex
P.S. Chiudiamo questo inutile post e procediamo invece con quello
ricorsione/iterazione che e' piu' costruttivo.

 una assert in tutte le funzioni che utilizzano quel puntatore.
Ah, su questo siamo completamente concordi. Il mio non era un tentativo di
rendere veramente sicuro un programma, ma solo di un poco.
Vedi, mi dispiace solo di non aver capito cosa intendevi, ma se tu mi
dovessi smentire (con la risposta a questo msg) sarei contento di aver
capito un nuovo concetto. Insomma parlare con persone "normali", come hai
fatto tu, non puo' essere altro se non costruttivo. La cosa cambia invece
quando non si riesce ad avere dialogo...
Alex

 Non capisco che cosa tu voglia dire, mi dispiace...
Immagina di utilizzare in modo improprio un puntatore invalidato. Sei
nella zona di "undefined behavior" e quindi può succedere di tutto. Ma
la cosa forse peggiore che possa succedere è... niente. O almeno, niente
nel momento in cui viene eseguita l'istruzione incriminata. Il programma
procede tranquillo e beato e va ad incasinarsi mezz'ora più tardi.
Assegnando NULL al puntatore, quindi, praticamente forzi il
comportamento peggiore. Il programma non darà alcun avviso di errore ma
è comunque un programma errato in quanto sta utilizzando un puntatore
che non era previsto utilizzasse.
Se non è ancora chiaro dimmelo pure.
EMG

 che non era previsto utilizzasse.
Vediamo se ho capito... e' meglio "ricevere" subito un errore piuttosto che
non riceverne nessuno e magari non avere il risultato che ci si aspetta....
Esempio : Se dopo aver cancellato l'albero provo a stamparlo:
puntotore non NULL: mi da errore.
puntatore NULL : non mi da errore ma non stampa nulla. Magari mi attendo la
stampa e non capisco quale sia il problema...
In questo caso quello che dici e' verissimo, anche se dipende dai punti di
vista.
Quello che dici e' verissimo, ma dipende anche da cosa intendi per "sicuro"
ed in generale su che tipo di programma.
Ora provo a spiegarti io cosa intendo:
Immagina di avere un programma che scrivendo INS n inserisce un numero,
scrivendo FIND n trova un numero, scrivendo DELMAX cancella il valore
massimo e  STAMPA stampa il contentuto in ordine etc...
Bene il programma ha questa semplice interfaccia "run-time". Immagina ora di
aver inserito 10 numeri con INS n.
Se cancello con DELMAX il nodo con valore piu' grande, o magari ne cancello
3 tutto va bene anche quando dopo scrivo STAMPA.
Il problema e' che se a forza di INS e DELMAX svuoto l'albero (scrivendo
piu' DELMAX che INS) poi quando chiamo STAMPA il programma si "blocca".
Non sarebbe meglio (in questo caso) se il puntatore tornasse a valere NULL e
STAMPA non facesse nulla oppure (MOLTO MEGLIO) scrivesse (con il codice
proposto da Luca) la chiara stringa Albero vuoto ?!?
Ora, per concludere, ho capito, quello che dici ed e' verissimo. Mi accorgo
di aver esagerato quando ho scritto : "Quindi questo e' un errore". Non e'
un errore. Dipende da cosa si programma e da cosa si preferisce. Alcuni
programmi necessitano di un accorgimento simile al mio, mentre altri si e
no.... insomma, per gli altri programmi dipende dalle preferenze:
C'e' chi preferisce non ricevere errori a scapito di magari avere qualche
difficolta' in piu' a trovare un eventuale BUG (che ha meno probabilita'
pero' di accadere), ed altri che preferiscono ricevere errori ma risolvere i
BUG con maggiore facilita' !
Ti devo ringraziare, visto che non avevo tanto preso in considerazione anche
il secondo aspetto...
Alex

  }
In verità quello che ho detto io valeva per alberi a chiave unica. Con un
inserimento di questo tipo vengono ovviamente inserite chiavi uguali, e
questo provoca un notevole peggioramento per quanto riguarda il
bilanciamento dell'albero.
Ma non mi pare che l'albero di cui parlavate fosse a chiave unica quindi ciò
che ho detto era sbagliato.

alle stesse prestazioni.
non è vero. Pensa al fattoriale: iterativo è un ciclo senza alcun uso
di stack e memoria aggiuntiva; ricorsivo è tutta un'altra cosa.
Anto
--
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

  }


 che ho detto era sbagliato.
Infatti parlavamo di alberi in generale: con input ordinati, a chiave unica,
random etc... Insomma una funzione generale che vada "bene" un po' con tutti
i tipi (anche se con input ordinati l'albero non e' davvero la struttura
ideale!).
Inoltre un albero di +1.267.650.600.228.229.401.496.703.205.376 nodi (2^100)
come farebbe ad essere a chiave unica. Il mio computer ha 32 bits ce ne sono
con molti piu' bits, ma ....  ci vuole una bella fantasia a farlo a chiave
unica con tanti nodi (scherzo).
Comunque con insert(&tree,rand()%10000); e profondita' massima 8: while(d<8)
non ottengo 256 inserimenti, ma solo : 18. Con stampalbero ho controllato
tutti gli input e sono a "chiave unica":
41 491 1478 1942 2995 3281 4464 5705 5724 6334 6500 6827 6962 8145 8467 9169
9358 9961   Inserimenti: 18  Press any key to continue
(se ti interessa ti posto anche l'ordine con cui i valori sono stati
inseriti (random) nell'albero).
Ora questo esempio e' MOLTO POCO indicativo visto che e' fatto sui piccoli
numeri, ma nonostante sui grandi numeri le cose stiano un poco diversamente
non si arriva mai a 2^d inserimenti e nemmeno vicino (per arrivare a
profondita' d. In altre parole un albero non avra' praticamente mai altezza
log(n) con input random. Se lo ordini invece, ovviamente, SI).
Alex

funziona!!!!!
non appena ho inizializzato *ptr = NULL gia' funzionava (non alla perfezione
ovviamente).
Cmq ho ottimizzato pure il codice con i vostri consigli.
Grazie di esistere raga' :))
Ciao,
Luca
"Alex" <nom...@bow.wow> ha scritto nel messaggio
news:EEYZ6.7271$6x.3...@news.infostrada.it...


BUG con maggiore facilita' !
Tra le due categorie, la seconda e' quella dei programmatori.

non č vero.
Stiamo parlando del caso specifico degli alberi, spero tu te ne
sia accorto.

 il secondo aspetto...
Siamo qui per discutere ed imparare.
EMG

quindi ti invito a stare attento a moderare il linguaggio.
Ma vaffanculo !
*PLONKISSIMO*
--
Andrea Laforgia - walkietalkie(at)
libero.it
#exclude <windows.h>

 Tra le due categorie, la seconda e' quella dei programmatori.
Come al solito tu liquidi tutto con una frase. Ho fatto l'esempio di un
programma che necessita di tale accorgimento, sia per la stampa che per gli
inserimenti successivi allo svuotamento dell'albero.
Ma... ok, sto al tuo gioco parliamo solo delle 2 categorie nei casi in cui
tale accorgimento non e' "obbligatorio":
EMG ha ragione quando dice che potrebbe rendere piu' difficile
l'individuazione di alcuni problemi, quindi anche tu hai ragione se segui
questa tesi, ma il fatto e' che tu come al solito esageri e tiri conclusioni
piu' grandi di te!
D'altro canto ho anche spiegato che tale accorgimento rende anche piu'
difficile che accadano dei problemi quindi occorre valutare bene cosa
convenga fare a seconda del programma e di chi lo usera'. Ho fatto anche un
esempio di un programma su cui poco bisogna valutare, bisogna usare un
qualche accorgimento, visto che la tua funzione (senza tale accorgimento)
sarebbe solo causa di grossi problemi.
Alex

 sia accorto.
Ma allora non sei scontroso solo con me ;-)
Dal modo in cui hai impostato quel discorso non era cosi' chiaro che tu
parlassi del caso specifico degli alberi (che al massimo sarebbe
dell'inserimento di un nodo in un albero e non degli alberi in generale che
ad esempio necessitano della ricorsione per la stampa in ordine).
Ma ovviamente sapendo che sai programmare ho capito che ti riferivi al caso
specifico.
E se parlavi del caso specifico, come penso non e' che sia molto meglio
pero',  visto che vuole dire che non ti sei accorto del fatto che si
traduceva con un semplice ciclo senza alcun "meccanismo" !!!
Inoltre quando Antonio diceva "Pensa al fattoriale: iterativo è un ciclo
senza alcun uso
di stack e memoria aggiuntiva" intendeva dire che l'inserimento segue
esattamente lo stesso schema: e' una ricorsione che si traduce con un
semplice ciclo (gia' ti ho scritto questo in un altro messaggio).
Insomma credo si fosse accorto che si parlava di alberi ed ancora una volta
ti ha provato di dire: quando la ricorsione si traduce con un semplice ciclo
andrebbe sempre tradotta in iterazione. Quando come nel caso di fibonacci
(bad recursion) si ricalcolano alcuni valori piu' volte bisognerebbe trovare
un modo iterativo per evitarlo. In fine quando l'iterazione e' troppo
complicata e non fa altro che imitare la ricorsione usando uno stack allora
conviene usare la ricorsione direttamente ed avere un codice piu' leggibile
e semplice. (vedi stampalbero).
Alex

risolvere problemi  in maniera iterativa in maniera efficente.
Una volta un mio amico ha notato che basta spostare l'anello
piu' piccolo a destra (con rientro 3->1) nelle mosse dispari.
Nelle mosse pari si fa l'unica mossa legale che non sposta
l'anello piccolo.
Detto a parole e' una soluzione "semplicissima" ma tradotto
in codice diventa comunque abbastanza complesso rispetto
alla banale soluzione ricorsiva.
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

tua idea e farai ancora funzioni insicure.
Oh... beh... se era una guerra privata allora mi chiamo fuori...


 Siamo qui per discutere ed imparare.
si, discutere, imparare, insegnare, divertirsi,  etc... ;-)
Alex

 Ma vaffanculo !
Ma e' mai possibile che tu te la debba prendertela per cosi' poco ?!?
Esistono problemi piu' grossi nella vita che non quello di aver sbagliato un
post sulla ricorsione/iterazione e di aver fatto 2-3 programmi sbagliati
parecchio tempo fa.
Appena uno va OT lo bastoni subito !
Appena uno risponde sopra il quote e non sotto ti incazzi !
Insomma sei cosi' pignolo nei confronti della netiquette che non rispetti la
regola principale: non essere volgari.
Incomincio a pensare che tu creda che le regole esistano solo per gli altri.
Sappi che a me il tuo v******o non mi tocca, credi che ora io ci soffra ?!?
Ti ho chiesto di non diventare volgare solo per la decenza tua e di questo
NG.
Anzi rido a vedere quanto tu sia infantile. Ti dico una cosa: se anche tu
fossi il piu' bravo programmatore del mondo non ti invidierei mai, visto che
vali molto poco come uomo.
Alex
P.S. visto che ci tieni tanto siamo OT, rispondi pure, ma non lamentarti poi
se ti fanno presente che i nostri litigi (o meglio i tuoi) non sono di
interesse del NG.

 Oh... beh... se era una guerra privata allora mi chiamo fuori...
E' privata nel senso che e' di Andrea. Ad ogni modo non chiamarti fuori,
altrimenti diventa veramente una guerra privata ed invece siamo su di un NG
pubblico sul quale si dovrebbe discutere in modo costruttivo. (con quella
frase non mi riferivo a questo argomento in particola, ma in generale)
Alex

molto piu' chiare leggendo quel post.
Non ho letto tutti i post. Purtroppo devo confessare che leggo
solo una piccolissima parte di quanto viene scritto in questo
e degli altri newsgroup che seguo (per questioni di mancanza
di tempo). La decisione di cosa leggere e' presa in base al
topic e/o all'autore... ma spesso anche dal caso.
-- tornando agli alberi --
Secondo me e' lodabile l'idea che quando cancelli un nodo devi
anche fare in modo che chi vi stava puntando non vi punti piu'...
ma la soluzione che preferisco in questi casi non e' passare
un puntatore di puntatore. Io uso di solito strutture che si
possono anche navigare "al contrario"... es:
  typedef struct NODO
  {
    ... dati del nodo ...
    struct NODO *child[2];  /* Puntatori sx/dx */
    struct NODO *pop;       /* Puntatore al padre */
    int side;               /* Su quale lato mi trovo ? */
  } Nodo;
In questo modo e' possibile eliminare un nodo dall'albero noto
solo il puntatore al nodo.
   void EliminaNodo(Nodo *n)
   {
     if (n)
     {
       EliminaNodo(child[0]);
       EliminaNodo(child[1]);
       ... elimina dati posseduti dal nodo ...
       if (n->pop) n->pop->child[n->side]=NULL;
              else root=NULL;
       free(n);
     }
   }
In alternativa si puo' usare anche un "backptr" piu' fisico
(nel caso si voglia risparmiare spazio e non interessi
navigare verso l'alto dell'albero da un punto di vista
logico come -- es. dato un nodo trovare suo "fratello")
  typedef struct NODO
  {
    ... dati del nodo ...
    struct NODO *child[2];  /* Puntatori sx/dx */
    struct NODO **backp;    /* Contro-puntatore */
  } Nodo;
  void EliminaNodo(Nodo *n)
  {
    if (n)
    {
      EliminaNodo(child[0]);
      EliminaNodo(child[1]);
      ... elimina dati posseduti dal nodo ...
      *(n->backp)=NULL;
      free(n);
    }
  }
Se invece usi come proponi tu semplicemente azzerare il
puntatore passato non hai garanzie che quello che ti
passano sia effettivamente l'unico puntatore "ufficiale"
al nodo. Es:
   Nodo *p=root; /* Ora p punta alla radice */
   EliminaNodo(&p);
   /*
   ** Ora p sara' anche NULL ... pero' root (che
   ** e' il puntatore ufficiale!!!) punta a dei
   ** dati che sono stati deallocati.
   */
Quindi a mio parere questa soluzione e' piu' astrusa da
usare (&p) e non offre nessuna garanzia reale in piu'.
Io sono un patito delle strutture in cui tutte le
operazioni siano O(1) se logicamente sensato... ad esempio
la mia lista standard e' sempre doppiamente collegata
e con puntatori al padre...
  typedef struct POINT
  {
    struct POLYGON *pop;
    struct POINT *prev,*next;
    double x,y,z;
  } Point;
  typedef struct POLYGON
  {
    struct POINT *first,*last;
  } Polygon;
I puntatori "all'indietro" diventano fra l'altro spesso
praticamente necessari quando crei strutture dati
complesse in cui ogni elemento e' contemporaneamente
parte di piu' strutture di accesso distinte... es. uno
stesso elemento e' contemporaneamente in una lista, un
albero binario e una hash table.
Di queste strutture complesse che spesso utilizzo ho
scritto qualcosa sulla mia homepage:
http://netservers.com/~agriff/showpage.cgi?page=net.pml
Chiaro che tutto dipende da cosa ci si vuol fare... in
alcuni casi ho anche usato alberi con nodi a N figli
che usano solo un puntatore per nodo padre (tutti i
figli sono allocati in un unico array di nodi contigui)
o cose ancora piu' astruse.
Siamo nel campo delle opinioni, ovviamente... la tecnica
che hai consigliato tu comunque non mi ha mai attirato:
"sembra" piu' sicura... ma non offre secondo me un granche'.
HTH


 I puntatori "all'indietro" diventano fra l'altro spesso
Hai perfettamente ragione ! Abbiamo pero' lavorato con la struttura data dal
professore di luca:
typedef struct nodo
    {
    int key;
    struct  nodo  *left,  *right;
    }NODO;
Quello che dici e' verissimo e presto faro' un salto alla tua homepage.
Alex

 nullo) ?!?
Infatti non dovrebbe mai diventarlo. Ma qui stiamo parlando di
condizioni di errore e quelle, purtroppo, non sono prevedibili.
EMG

>>Per la tua "soluzione" sarebbe tutto in ordine...
Anche per l'altra, no ?
Insomma entrambe le versioni quando ricevono un puntatore NULL non si
lamentano. Si lamentano invece quando ne ricevono uno non valido. Io facevo
in modo che quelli non validi diventassero NULL e quindi il programma non si
lamentasse. Ho capito che questo, in alcuni casi, puo' indurre a problemi
maggiori, ma... anche per l'altra soluzione sarebbe stato tutto in ordine.
(almeno mi sembra di ricordare cosi' !)
Spero di non essermi perso, sto incominciando a far fatica a tenere il conto
di tutti questi post e di ogni post ricordarmi il relativo programma con i
suoi pregi e difetti ;-)
Alex

sia accorto.
a me sembrava che il discorso si fosse spostato sulla ricorsione in
generale... cmq puň darsi che io abbia capito male (o che tu ti sia
spiegato male).


 lamentano. Si lamentano invece quando ne ricevono uno non valido.
Penso che stai confondendo nuovamente i livelli. Per il livello
implementativo il concetto di puntatore non valido può essere molto
diverso da quello del livello utente. Il livello implementativo dovrebbe
garantire al livello utente una visione sufficientemente astratta e
controllata del concetto di puntatore, un po' come fanno le funzioni di
gestione dei files che ci mostrano un concetto astratto di FILE che
corrisponde ad una serie di dettagli implementativi dei quali non
dobbiamo preoccuparci.
EMG