Albero con cancellazione di nodo

nadia891
Questa volta l'esercizio richiede un albero binario con cancellazione di un nodo inserito da utente.
Ho utilizzato la funzione successore in modo che se il nodo non è una foglia si possa sostituire con un altro nodo e potendo così cancellarlo.
/*Visita dell'albero binario */

 /*Ricerca e cancellazione del sottoalbero*/
 
 
 
#include <stdio.h>
#include <stdlib.h>


struct node{
  int inf;
  struct node *albSin;
  struct node *albDes;
  };
  
  struct node *radice; /*puntatore alla radice dell'albero*/
  struct node **trovato=NULL;/*puntatore al valore da ricercare*/
  
   
   
   
  struct node *albBin(void);
  struct node *creaNodo(struct node *p,int val);
  void ricBin(struct node *p,struct node *q,struct node **pEle);
  struct node *cancella(struct node *p,int val);
  struct node *successore( struct node *p);
  
  
  
  
  int main(void)
  {
   
   struct node *p;
   int n;
   
   radice=albBin();/*crea l'albero binario*/
   
   
   printf("\nInserisci nodo che vuoi cancellare:");
   scanf("%d",&n);
   p=cancella(radice,n);
   free(p);
   
  return 0;
  
   }
   
   
   
   
   struct node *albBin(void)
   {
    struct node *p=NULL;
	int n;
	
	do{
	 printf("\nInserire una informazione (0 per finire):");
	   scanf("%d",&n);
	  
	  
	   if(n!=0)
	    p=creaNodo(p,n);
		}
		while(n!=0);
		
		return (p);
		}
		
	   
	
	
	struct node *creaNodo(struct node *p,int val)
	{
	 if(p==NULL){
	 p=malloc(sizeof(struct node));
	 p->inf=val; /*inserimento di etichetta*/
	 p->albSin=NULL;
	 p->albDes=NULL;
	 }
	 else
	 {
	 if(val > p->inf)/*val maggiore del campo inf della radice */
	   p->albDes=creaNodo(p->albDes,val);
	  else
	     if(val < p->inf)
        p->albSin=creaNodo(p->albSin,val);
      }
	  return (p);
	  }
	  
	  
	  
	  
	  
	  void ricBin(struct node *p,struct node *q,struct node **pEle)
	  {
	  
	  if (p!=NULL)
	    if(q->inf==p->inf){
		 
		  *pEle=p;/*a pEle è passato l'indirizzo di p 
		            visto che è stato trovato sarà diverso da NULL*/
		  }
		  else
		  if(q->inf <  p->inf){
		    ricBin(p->albSin,q,pEle);
			}
			else{
			  ricBin(p->albDes,q,pEle);
			  }
			  }
		
	  
	  
	  
	  
	  
	struct node *cancella(struct node *p,int val)
	{
	   struct node *w;
	 
	   
	  if(p!=NULL)
	   {
      
		
      if (p->inf==val)/*se il nodo è quello da cancellare*/
       {
		    if(p->albSin==NULL)
			  p=p->albDes;
			 if(p->albDes==NULL)
			  p=p->albSin;
			  
			  else
			     {
				   w=successore(p->albDes);/*w è il minimo del sottoalbero destro
				                       perchè è la foglia più a sinistra(quindi di inf minore) del sottoalbero destro 
										  perchè applicato a p->albDest*/
				  					  
				   p->inf=w->inf;/*sostiuamo p con w*/
				       /*per come è stato scelto w sarà maggiore di tutti i nodi del sottoalbero
					     p ,e minore di tutti i nodi del sottoalbero destro di p,
						   quindi lo può sostituire*/
						   
				   p->albDes=cancella(p->albDes,w->inf);/*poi cancelliamo w (in quanto contiene inf di p)
				                                        /*in questo caso sarà una cancellazione facile 
														 perchè per come lo abbiamo scelto non ha figli quindi si trovarà nel caso 
														 p==NULL di sopra*/
				   
				  }
		}
	   if (p->inf <val)/*se il nodo da cancellare ha chiave maggiore allora mi sposto a destra */
		p->albDes=cancella(p->albDes,val);
		else p->albSin=cancella(p->albSin,val);/*sennò mi devo spostare a sinistra*/
		
	  }
		 else
		 {
		   printf("\nElemento non presente\n");
		   exit(EXIT_SUCCESS);
		   }
		 
		  return p;
					 
		}			 
					 
					 
				
				
  struct node *successore( struct node *p)
   {
     while(p->albSin !=NULL)
	
	  p=p->albSin;
     
	
	 return p;
		 }
				   
	  
	  ]

Risposte
apatriarca
Per prima cosa credo dovresti cercare di formattare il tuo codice in modo un po' più uniforme in modo da rendere più facile la lettura. Credo dovresti poi dirci in cosa tu stia incontrando difficoltà.. Vuoi solo un parere sul codice? C'è qualcosa che non funziona? Che cosa?

nadia891
Sicuramente c'è qualche errore perchè quando inserisco i dati il sistema va in un ciclo infinito quindi sicuramente ho sbagliato qualcosa nel codice!

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.