Newsgroup: it.comp.lang.c++
Titolo: albero -> eliminazione ricorsiva

salve a tutti, questa procedura è copiata pari pari dal libro di
savy da c++ a uml
c'è qualcosa che non va nella procedura di eliminazione ma non riesco a 
capire cosa... questa procedura non genera errori in compilazione
grazie per l'aiuto.
/////////////////////////////////////////////////////////////
void stadio::sostituisce(A & p, A & a){
    A q;
     if(p -> des == 0){ //p -> des è il maggiore
       q = p;
       p = p->sin;
    	  q -> des = a -> des;
    	  q -> sin = a -> sin;
    	  a = q;
     }else
       sostituisce(p -> des, a);
}
///////////////////////////////////////////////////////////
void stadio::eliminaric(A a, int num){
   A s; //puntatore ausiliario per il delete;
   if(a != 0){
     if(num == a -> numero){
      s = a;
       if(a -> sin == 0)
        a = a -> des;
        else if(a -> des == 0)
          a = a -> sin;
          else
            sostituisce(a -> sin, a);
          delete s;
          eliminaric(a, num);
        }//fine if(e == a -> elem);
         else if(num < a -> numero)
          eliminaric(a -> sin, num);
           else
             eliminaric(a -> des, num);
    }//fine if(a != 0)
}
////////////////////////////////////////////////////////////

 capire cosa... questa procedura non genera errori in compilazione
Non ho capito nell'algoritmo il caso del nodo con 2 figli. nella 
cancellazione di un nodo in un albero binario puoi avere tre casi:
1) Nodo foglia: elimini direttamente il nodo
2) Nodo da eliminare con un solo figlio: scarti il nodo e connetti 
direttamente il padre del nodo da eliminare al figlio del nodo stesso
3) Nodo da eliminare con due figli: trovi il successore del nodo da 
eliminare e lo sostituisci. Il successore in un albero binario ordinato è il 
primo nodo figlio sx del sottoalbero destro del nodo da eliminare che non ha 
figlio sinistro. Colleghi il padre del successore al figlio destro del 
successore, sostituisci il valore del nodo successore col valore del nodo da 
eliminare, elimini il nodo successore.
Es. di un nodo ordinato sx >= nodo>= dx (E: Nodo da eliminare, S: 
successore)
                     2
                /          \
   E-->  5                1
         /        \
      8           4
                /       \
   S-->  6           3
               \
                6
Diventa:
                   2
                /       \
   S-->  6             1
         /        \
      8           4
                /        \
FDS--> 6            3      (FSS: Figlio Dx S)
La funzione "sostituisce" mi pare sbagliata (anche lasciando perdere i 
passaggi per reference di p e a). Al posto di quella farei una funzione 
Successore:
//...
          else {
                A* nodo = Successore(p -> des, a);
                "copia valore di nodo nel valore di a"
                delete nodo;
          }
A* stadio::Successore(A & n, A & p){ //P:nodo padre di T
    if (n.des!=NULL)
        return successore(n.sin,n);
    else //successore n trovato (il padre è p)
            if (n ==  p.sin)
                   p.sin = n.des;
            else //nodo successore figlio dx del nodo da eliminare
                   p.des =  n.des;
    return &n;
}
Ciao
Andrea