Newsgroup: it.comp.lang.c++
Titolo: [LUNGO] Problemi strutture dinamiche: alberi binari

ciao a tutti,
tempo fa ho scritto un post per evidenziare alcuni mie "indecisioni" 
sulle liste concatenate..risolti, anche grazie al vostro aiuto, quei 
problemi, ho provato a cimentarmi con l'implementazione degli alberi.
Tutto è andato bene fino agli ultimi 2 metodi :(..la cancellazione di un 
nodo a scelta e la distruzione dell'albero.
Riporto per chiarezza alcuni pezzi di codice.
//STRUTTURA DEL NODO
template <typename T>
class Nodo_albero {
     private:
         friend class Albero<T>;
         Nodo_albero<T> *sin;
         Nodo_albero<T> *dx;
         T dato;
     public:
         T RecuperaDato();
         Nodo_albero(T ele, Nodo_albero<T> *s=NULL, Nodo_albero<T> 
*d=NULL): dato(ele), sin(s), dx(d) {};
};
//INTERFACCIA ALBERO
template <typename T>
class Albero {
     private:
         Nodo_albero<T> *radice;
         int altezza;
     public:
         Albero(){ radice = NULL; altezza = 0; }
         ...
         ...
         void cancella_nodo(T);
         void Distruggi_albero(Nodo_albero<T> **);
         ~Albero(){ Distruggi_albero(&radice); }
};
L'implementazione dei metodi "difettosi" è:
//METODO PER LA CANCELLAZIONE DI UN NODO
template <typename T>
void Albero<T>::cancella_nodo(T ele)
{
	Nodo_albero<T> *curr = radice,*succ,*prec;
	int flag=0,delcase;
	//Procedimento per trovare la posizione del nodo
	while(curr!=NULL && flag!=1)
	{
		if(ele < curr->dato)
         {
			prec = curr;
			curr = curr->sin;
		}
		else if(ele > curr->dato)
         {
			prec = curr;
			curr = curr->dx;
		}
		else //curr->dato = ele
         {
			flag=1;
		}
	}
	if(flag==0){
		cout<<"\nL'elemento non si trova nell'albero\n";
		return;
	}
	//Decisione sul tipo di cancellazione
	if(curr->sin==NULL && curr->dx==NULL)
		delcase=1; //Il nodo non ha figli
	else if(curr->sin!=NULL && curr->dx!=NULL)
		delcase=3; //Il nodo ha entrambi i figli
	else
		delcase=2; //Il nodo contiene solo un figlio
	//Tipo di cancellazione 1
	if(delcase==1){
		if(prec->sin == curr) //se il nodo è un figlio sinistro
			prec->sin=NULL; //assegna il puntatore del suo genitore
		else
			prec->dx=NULL;
		delete(curr);
	}
	//Tipo di cancellazione 2
	if(delcase==2){
		if(prec->sin==curr){ //se il nodo è un figlio sinistro
			if(curr->sin==NULL)
				prec->sin=curr->dx;
			else
				prec->sin=curr->sin;
		}
		else{ //prec->dx=curr
			if(curr->sin==NULL)
				prec->dx=curr->dx;
			else
				prec->dx=curr->sin;
		}
		delete(curr);
	}
	//Deletion case 3
	if(delcase==3){
		succ = trova_succ(curr); //Trova il successore in ordine
                                 //del nodo.
		int ele1 = succ->dato;
		cancella_nodo(ele1);  //Cancella il successore
		curr->dato = ele1; //Sostituisce il dato con il dato del successore. 
	}
}
//METODO PER LA DISTRUZIONE DELL'ALBERO
template <typename T>
void Albero<T>::Distruggi_albero(Nodo_albero<T> **ptr)
{
     if((*ptr) != NULL)
     {
		Distruggi_albero(&(*ptr)->sin);
		Distruggi_albero(&(*ptr)->dx);
		delete(*ptr);
	}
}
Il metodo per la cancellazione funziona correttamente per tutti i casi 
provati tranne uno: se inserisco gli elementi dell'albero in modo che si 
dispongano tutti su un "versante" dell'albero (ad es. 
1(radice)-2-3-4-5-6-7), richiamando il metodo cancella_nodo per la 
radice, l'esecuzione si interrompe e il controllo ritorna al sistema 
operativo. In tutti gli altri casi il metodo funziona (compresa la 
cancellazione di radici di alberi disposti in modo diverso)..
Per quanto rigurda il metodo per la distruzione, il compilatore non 
segnala errori, ma l'albero non viene cancellato. Se infatti richiamo il 
metodo per la distruzione e poi provo a reinserire gli elementi presenti 
in precedenza nell'albero, il programma mi segnala che tali elementi 
sono già presenti (segnalazione che ho previsto io, trattandosi di un 
albero binario di ricerca), segno che non è stato cancellato un bel niente.
Potete dirmi dove sbaglio?
Grazie
Phate

Mi manca ancora da analizzare un caso... ma a occhio e croce hai almeno due 
problematiche:
Se elimini il nodo che si trova sulla "radice" non aggiorni la variabile 
membro radice.
Se cerchi di eliminare il nodo radice, prec ha valore non definito. Ma sta 
attento se ci metti valore NULL che lui non si metta a usarlo lo stesso!!
Ma adesso dimmi... stai per caso sperimentando il tuo programma con un 
compilatore a riga di comando? No, perchč queste cose facendo un po' di 
debugging sarebbero uscite... Inoltre per esempio certi debugger ti avvisano 
se provi a usare una variabile non inizializzata.
Non ho ben capito come fai il caso delcase = 3... il metodo "classico" per 
alberi non bilanciati dovrebbe essere quello di collegare il nodo padre del 
nodo da cancellare con il nodo figlio di quello da cancellare e poi 
collegare l'altro figlio da qualche parte al primo figlio (sě, lo so, č 
veramente mal spiegata)
10
|
6-7-8
|
4-5
|
3
Vuoi eliminare il 6. Colleghi il 10 con il 4
10
|
4-5
|
3
Ora ti resta da collegare il ramo 7-8. Parti da 4 e cerchi il nodo libero 
piů adatto. Da 4 vai a 5 che per fortuna ha rami liberi a cui collegarlo. 
Questo ovviamente non č garantito. Potresti dover attraversare vari nodi.
--- bye 

 
mi ero dimenticato di specificare cosa faceva il metodo trova_succ :
Nodo_albero<T> * Albero<T>::trova_succ(Nodo_albero<T> *curr)
{
	Nodo_albero<T> *succ=curr->dx; //Si sposta al sottoalbero destro
	if(succ!=NULL){
		while(succ->sin!=NULL)	//Se il sottoalbero destro non è vuoto
			succ=succ->sin;
	}
	return(succ);
}
Ora il metodo di cancellazione del nodo sembra funzionare, ma non riesco 
a risolvere quello per la distruzione dell'albero. Ho provato a 
implementarlo diversamente richiamando il metodo cancella_nodo sulla 
radice dell'albero fino a quando quest'ultima non punta a NULL:
template <typename T>
void Albero<T>::Distruggi_albero(Nodo_albero<T> *ptr)
{
     while(ptr != NULL) cancella_nodo(ptr->dato);
}
ma mandato in esecuzione il programma entra in un loop infinito che non 
riesco a spiegarmi..hai altro che mi possa illuminare?:)
Grazie
Phate

     while(ptr != NULL) cancella_nodo(ptr->dato);
Adesso... Mi spieghi chi o cosa modifica ptr? La risposta è: NESSUNO. Quindi 
come minimo qui c'è un errore.
Prova con
while (ptr->sin != NULL) cancella_nodo(ptr->sin->dato);
while (ptr->dx != NULL) cancella_nodo(ptr->dx->dato);
cancella_nodo(ptr->dato);
Inoltre questa funzione mostra appieno l'inefficienza della classe come 
l'hai strutturata. Lui sa benissimo dove si trova il nodo che gli interessa, 
ma ogni volta dovrà andarselo a cercare.
In generale una classe del genere dovrebbe avere un iteratore (leggiti le 
STL per scoprire cos'è) E una funzione di ricerca per associare un dato con 
un iteratore. Inoltre il tuo metodo di ricerca lavora sul principio che dato 
sia univoco (non ci sono due elementi 5). Ora, se dato è per esempio un 
codicefiscale va anche bene, ma se dato è un'età no.
--- bye