Newsgroup: it.comp.lang.c
Titolo: ! Alberi binari 2 ?|?

Ah, dimenticavo:
se cancello un nodo devo anche settare che il padre del nodo->left o right
ora e' uguale a NULL. Come faccio a sapere quale e' il padre di un nodo con
una struttura priva del campo prev, ma solo cosi':
struct Btree{
    int val;
    struct Btree* left;
    struct Btree* right;
};
Insomma, ho dei problemi a cancellare i nodi !!!
Riesco a stampare l'albero, ad aggiungere nodi etc, ma a cancellarli no.
Il mio libro dice: father(p)->left , grazie, ma come implemento questa
funzione ?
Grazie ancora,
Ricky


non sono sicuro al 100%, ma penso che, come per le liste collegate, devi
usare
due puntatori alla struttura, in modo che quando quello di controllo
coincide con
quello che stavi cercando, quello precedente ti permette di cancellare,
o inserire
una nuova struttura ...
es (per una lista, e applicabile (penso) anche agli alberi binari )
struct ant *pre, *post;
pre = head; post = head->next;
muovendoti poi in avanti con :
post = post->next; pre = pre->next;
arrivi con il far coincidere post con la struttura che vuoi cancellare
...
dopo fai :
pre->next = NULL;
e la struttura post non c'e' piu' nella lista ....
per inserire e' la stessa cosa :
sposti in avanti fino a quando la chiave di ordinamento di post non e'
maggiore
della chiave della nuova struttura e poi :
pre->next = new;
new->next = post;
penso che sostituendo next con left e right, questo principio funzioni
anche
con gli alberi binari.
spero di esserti stato utile (non ne sono sicuro !!!)
ciao ciao
-- 
Antonio barbone ......
Outside of a dog, a book is man's best friend.
Inside of a dog, it's too dark to read.
		-- Groucho Marx

...


 wrote in message
uC885.18922$2s6.2...@news.infostrada.it...


"int n"  che significato ha?
Mamma mia ma scusa ma te le basi del C le conosci o no ?
Augusto Pucci
Webmaster di Prospektiva On-line
http://www.prospektiva.it

"int n"  che significato ha?
n contiene il valore che devo cancellare. In altre parole devo cancellare il
nodo il cui campo ->val sia == a n .
Ricky

 Ricky
non potresti indicare ad esempio come prototipo :
struct Btree *Deletenode (struct Btree *p, int n);
poi inizializzi un puntatore a struttura con la struttura head :
struct Btree *p_btree;
p_btree = head;
e richiami la funzione con :
while (p_btree = Deletenode (p_btree, n));
e nella funzione Deletenode indichi :
return (p);    /* che sarebbe il puntatore che hai incrementato nel caso
in cui n non
                  coincida */
per la cancellazione del primo campo devi effettuare il controllo
iniziale della
struttura head e, nel caso coincida con la chiave di cancellazione,
basta fare :
head = head->next;
dopo la cancellazione del campo fai :
return 0;
in modo che il programma esce dalla routine while ....
nella funzione penso che puoi procedere con i due puntatori, come ti ho
scritto nell'
altra e-mail ...
N.B.
quello che ti ho detto e' una mia "creazione" personale, quindi non so
se sia il
modo standard di procedere e, sicuramente, ci saranno metodi piu' validi
.... e
poi non ho il riscontro pratico del funzionamento .... comunque io ti ho
dato
l'imbeccata, e ora a te cercare di implementarla o, se ci riesci, di 
migliorarla ...... 
comunque ho fatto del mio meglio ....
sto iniziando anch'io ad usare gli alberi binari e, se imparo qualcosa
di nuovo,
te lo faro' sapere ....
ciao ciao ...


Salve, 
se ho capito il problema il nodo da cancellare potrebbe non essere una
foglia quindi devi decidere cosa fare dei due figli. Segue un eventuale
soluzione. 
Se puoi utilizza una funzione del genere: 
void DeleteNode(struct Btree* p, int n) {
   if (p->val!=n){
     if (p->left!=NULL) DeleteNode(p->left,n); 
     if (p->right!=NULL) DeleteNode(p->right,n); 
   }
   else {
     Btree* temp = p; 
     if (p->left==NULL) // debbo copiare solo il destro
        { p = p->right; delete(temp); }
     else if (p->right==NULL) // debbo copiare solo il sinistro
          { p = p->left; delete(temp); }
          else { /* if ((p->right!=NULL) && (p->left!=NULL))*/
            // devi decidere che cosa fare di uno dei due figli
          }
   } }
che IMPONE una chiamate tipo
    if ((root!=NULL) ) DeleteNode(root,n); 
Nel caso siano entrambi uguali a NULL fa due operazioni in piu'.  NON ho
provato questa funzione, ma credo funzioni, inoltre diminuisce il
numero di passi ricorsivi.

 wrote in message
QRj85.20999$2s6.2...@news.infostrada.it...

In linea di principio potresti suddividere il problema in due parti:
1) Verificare se la radice ha valore n ed in questo caso distruggere l'
intero albero.
2) Utilizzando la funzione ricorsiva col prototipo da te definito iniziare
dalla radice verificando se uno dei
   due figli del nodo corrente (struct Btree* p) ha il valore n e quindi se
affermativo distruggere il ramo in questione, se no procedere nello stesso
modo con i figli (questo non è comunque l' unico modo di procedere nell'
attraversamento di un albero).
Servirà quindi un' altra funzione ricorsiva che ha il compito di distruggere
i sottorami di un dato nodo.
ad esempio : DeleteSubTree(struct Btree* p)
In questo modo lavorando già sul nodo genitore non hai bisogno di fare un
passo indietro per aggiornare il padre a NULL. (strategia nota come "look
ahead"  ovvero guardare avanti)
A questo punto occorre considerare il fatto che di nodi con valore n nell'
albero ve ne possono essere più di uno e quindi decidere se eliminarli tutti
o fermarsi dopo avere trovato il primo. Inoltre , come annotato sopra,  ha
importanza la strategia di attraversamento dell' albero :
In profondità, prima il ramo sinistro oppure prima il ramo destro oppure
verifica prima il nodo di partenza ?
La scelta di una diversa opzione implica comportamenti totalmente differenti
della funzione !