Newsgroup: it.comp.lang.c
Titolo: Problema con la cancellazione dei nodi!

Ciao a tutti e scusate se continuo a rompere...
Ho implementato un programma per inserire/cancellare nodi in un albero, e/o
stampare l'albero in ordine simmetrico...
Tuttavia se inserisco i nodi  4, 2, 6, 5 e poi provo a canellare il nodo 4 e
quindi il nodo 5 mi viene detto che il nodo 5 non esiste! Eppure stampando
l'albero in ordine simmetrico il nodo 5 c'è eccome!
Il codice è il seguente:
--------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
struct intree
{
 int dato;
 struct intree *left, *right, *padre;
};
typedef struct intree inttree;
void inorder(inttree *root)
{
 if(root!=NULL)
  {
   inorder(root->left);
   printf("%d\n",root->dato);
   inorder(root->right);
  }
}
inttree* TreeSearch(inttree *root, int k)
{
 if((root==NULL)||(k==root->dato))
  return root;
 if(k<root->dato)
  return TreeSearch(root->left,k);
 if(k>root->dato)
   return TreeSearch(root->right,k);
}
inttree* TreeMaximum(inttree *root)
{
 while(root->right!=NULL)
  root=root->right;
 return root;
}
inttree* newnode()
{
 return(malloc(sizeof(inttree)));
}
void TreeInsert(inttree *root,inttree *z)
{
   inttree *tmp;
     tmp=root;
      while(1)
 {
       if(z->dato < tmp->dato)
  {
              if(tmp->left==NULL)
    {
                   tmp->left=z;
     z->padre=tmp;
                   return;
               }
   else
    tmp=tmp->left;
          }
 else if(z->dato > tmp->dato)
  {
              if(tmp->right==NULL)
    {
                   tmp->right=z;
                   z->padre=tmp;
     return;
               }
   else tmp=tmp->right;
          }
 else if(z->dato==tmp->dato)
  {
              printf("\nErrore Valore:
%d\nGia'Esistente...!!!\n\n",tmp->dato);
              return;
          }
      }
}
inttree * TreeDelete(inttree *root,inttree *z)
{
 inttree *s;
 if((z->left==NULL)&&(z->right==NULL))
  {
   if(z==root)
    {
     free(z);
     return NULL;
    }
   s=z->padre;
   if(s->left==z)
    s->left=NULL;
   if(s->right==z)
    s->right=NULL;
   free(z);
   return(root);
  }
 if((z->left!=NULL)&&(z->right)==NULL)
  {
   if(z==root)
    {
     s=z->left;
     free(z);
     return(s);
    }
   z->left->padre=z->padre;
   s=z->padre;
   if(s->left==z)
    s->left=z->left;
   if(s->right==z)
    s->right=z->left;
   free(z);
   return(root);
  }
 if((z->left==NULL)&&(z->right)!=NULL)
  {
   if(z==root)
    {
     s=z->right;
     free(z);
     return(s);
    }
   z->right->padre=z->padre;
   s=z->padre;
   if(s->left==z)
    s->left=z->right;
   if(s->right==z)
    s->right=z->right;
   free(z);
   return(root);
  }
 if((z->left!=NULL)&&(z->right!=NULL))
  {
   s=TreeMaximum(z);
   z->dato=s->dato;
   root=TreeDelete(root,s);
   return(root);
  }
}
main()
{
 int k;
 inttree *root=NULL, *z=NULL, *minmax, *successor, *cancella;
 while(1)
 {
  inizio:;
  printf("\nInserisci un numero(0 per terminare): ");
  scanf("%d",&k);
  if(k==0)
   {
    if(root==NULL)
     exit(1);
    while(1)
    {
     printf("\nChe vuoi fare?");
     printf("\n\n 1) Stampa in inordine");
     printf("\n 6) Cancella un nodo");
     printf("\n 9) Uscita\n\n");
     scanf("%d",&k);
     switch(k)
     {
      case 1: system("clear");
       printf("\n-----------------INORDER--------------------\n");
              inorder(root);
       printf("\n");
       break;
      case 6: printf("\nInserisci il nodo da cancellare: ");
       scanf("%d",&k);
       z=newnode();
       z=TreeSearch(root,k);
       if(z==NULL)
        {
         printf("\nIl nodo da cancellare non esiste!\n");
         break;
        }
       root=TreeDelete(root,z);
       if(root==NULL)
        goto inizio;
       break;
      case 9: exit(1);
       break;
     }
    }
   }
  z=newnode();
  z->dato=k;
  z->left=NULL;
  z->right=NULL;
  z->padre=NULL;
  if(root==NULL)
   {
    root=newnode();
    root->dato=k;
    root->left=NULL;
    root->right=NULL;
    root->padre=NULL;
   }
  else
   TreeInsert(root,z);
 }
}
----------------------------------------------------------------------------
---
Il problema penso sia nella routine di cancellazione, ma non ho capito dove!
Vi prego aiutatemi!
Grazie
Stefano


wrote:
[...]
probabilmente è sbagliata la funzione di cancellazione. ho visto che è
lunghissima ma non è proprio il caso, ti incollo qui un modo più
veloce e chiaro per implementare la cancellazione che penso si trovi
anche nella maggior parte dei libri:
void elimina_albero(Albero *vecchio) {
	Albero *punt, *nodo;
 	if (vecchio->sin == NULL || vecchio->des == NULL)
		punt = vecchio; 
	else
		punt = successore(vecchio); 
	if (punt->sin != NULL)
		nodo = punt->sin;
	else
		nodo = punt->des;
	if (nodo != NULL)
		nodo->padre = punt->padre;
	if (punt->padre == NULL)
		radice = nodo;
	 else 
    		if (punt == punt->padre->sin)
        			punt->padre->sin = nodo;
	    	else
			punt->padre->des = nodo;
	if (punt != vecchio) 
		vecchio->chiave = punt->chiave; 
	free(punt);
}
Albero *successore(Albero *nodo) {
	Albero *punt;
	if (nodo->des != NULL) {
		nodo = nodo->des;
		while (nodo->sin != NULL) 
			nodo = nodo->sin;
		return nodo;
	}
	punt = nodo->padre;
	while (punt != NULL && nodo == punt->des) {
		nodo = punt;
		punt = punt->padre;
	}
	return punt;
}
spero sia chiaro, i commenti li ho tolti perché erano lunghi e
venivano continuamente spezzati :-)

 wrote in message
3c6ac9c...@powernews.libero.it...


nodi rimangono a rompere le palle...
Puoi usare una funzione ricorsiva che esplora tutto l'albero, e quando
arriva in fondo risale facendo tutte le free.
Eccoti la funzione (visita inorder)... come vedi è veramente corta.
void tree_delete(struct intree *nodo)
{
  if(nodo != NULL)
  {
    tree_delete(nodo->left);
    tree_delete(nodo->right);
    free(nodo);
  }
}

On Wed, 13 Feb 2002 20:30:51 GMT, 
alanw...@freemail.it
 (alan) wrote:
Forse con le graffe aggiunte sotto il problema si risolverà.
Comunque la funzione dovrebbe chiamarsi "elimina_nodo", visto che non
elimina affatto l'intero albero...


fila e ogni volta essa mi deve allocare un'albero e poi cancellarlo...
mi sa che tu sei lo stesso della ML informaticamilano, dico bene?
ho visto che hai mandato una mail pure la, se mi viene una buona idea
ti ripondo in lista.
ciao