[C++] Cancellazione nodi da Alberi Binari, non capisco percè non funziona

[Skull260287]

Vi posto un codice da me scritto con l'ausilio delle slide del mio professore. Non capisco perchè non funziona ad esempio quando vado a cancellare un nodo diverso dalla radice o per la radice stessa in alcuni casi, vi prego di aiutarmi.

/*
   Note              : Algoritmi sugli alberi

*/     

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <math.h>


struct Anodo{
             int key;
             Anodo *left,*right;
             };

typedef Anodo *PAnodo;

using namespace std;

void StampaBST(PAnodo ,int );
void CreaAlberoDaFile(PAnodo &);
void InsertSort2( PAnodo &,int , bool &);
void LegaPadre(PAnodo , PAnodo , PAnodo , PAnodo &);
void DelTNode(int , PAnodo &, bool &);
void NuovoCandidato(int , PAnodo &, PAnodo &);
void Cerca(PAnodo , int , PAnodo &, PAnodo &);
void DammiChiave(PAnodo ,int &);

int main(){
    
    PAnodo A;
    
    CreaAlberoDaFile(A);
    
    StampaBST(A,0);
    
    int nodo;
    bool Done=false;
    cout<<"Inserisci i nodo che vuoi cancellare: ";
    cin>>nodo;
    DelTNode(nodo,A,Done);
    StampaBST(A,0);
    system("pause");

    return 0;
    
}

//Function per la cancellazione di un nodo

void LegaPadre(PAnodo OldChild, PAnodo NewChild, PAnodo Padre, PAnodo &Tree)
//collega il nodo genitore con il sottoalbero connesso al nodo da cancellare
{
  if (Padre==NULL)	//	{sostituiamo la root}
   Tree= NewChild;
 else
       if (OldChild ==Padre->left) 
       Padre->left=NewChild;  //	{sostituiamo al genitore il figlio sinistro}
       else 
       Padre->right=NewChild;  //	{sostituiamo al genitore il figlio destro}
}

void NuovoCandidato(int KeyValue, PAnodo &Candidato, PAnodo &Tree)
{	PAnodo Dummy; 	//variabile ausiliare per la chiamata a Cerca
	PAnodo Padre; PAnodo OldCandidato;
	int CandsKey;
OldCandidato= Candidato;

Cerca(OldCandidato->right, KeyValue, Dummy, Candidato);

OldCandidato->key= Candidato->key;

DammiChiave(Candidato, CandsKey);

Cerca(OldCandidato->right, CandsKey, Dummy, Padre);

if (Padre==NULL)
   LegaPadre(Candidato, Candidato->right, OldCandidato, Tree);
else  
   LegaPadre(Candidato, Candidato->right, Padre, Tree);
}

void Cerca(PAnodo Tree, int KeyValue, PAnodo &Node, PAnodo &Padre)
{
  int NodesKey;
  Padre=NULL;
  Node=Tree;
  DammiChiave(Node, NodesKey) ;
  while ((Node!=NULL) && (NodesKey!=KeyValue)) 
  {
      Padre=Node;
      if (NodesKey>KeyValue) 
         Node=Node->left;
      else
         Node=Node->right;      	
      DammiChiave(Node, NodesKey);
  }
}

void DammiChiave(PAnodo TNode, int &TheKey)
{ //ritorna il key field del nodo puntato da Tnode, se Tnode è 
                              // NULL allora ritorna il valore di -100
	if (TNode != NULL )
	    TheKey= TNode ->key;
	else
	 TheKey= -100;
}


void KillTNode(PAnodo Candidato){
     
     delete Candidato;
     }

void DelTNode(int KeyValue, PAnodo &Tree, bool &Done)
{   PAnodo Candidato; 	// puntatore al nodo candidato per la cancellatura
    PAnodo Padre; 		// puntatore al genitore del nodo candidato}
    int CandsKey;
    Done=true;
    Cerca( Tree,  KeyValue, Candidato, Padre);
    DammiChiave(Candidato, CandsKey);
    if (CandsKey!=KeyValue) 
       Done=false; 
   else
      if (Candidato->left==NULL)
         LegaPadre(Candidato, Candidato->right, Padre, Tree);
      else
         if (Candidato->right==NULL)   {
             LegaPadre(Candidato, Candidato->left, Padre, Tree);
	       }
         else
            NuovoCandidato(KeyValue, Candidato, Tree);
    KillTNode(Candidato);
}

void StampaBST(PAnodo Tree,int i){
    if(Tree!=NULL){
        StampaBST(Tree->right,i+1);
        for(int j=1;j<=i;j++)
            cout<<" ";
        cout<<Tree->key;
        cout<<endl;
        StampaBST(Tree->left,i+1);
    }
}

void CreaAlberoDaFile(PAnodo &Tree){
    int num;
    cout<<"Crea Albero da FILE:"<<endl;
    Tree=NULL;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeLn="albero.txt";
    filista.open(NomeLn.c_str());
    if(!filista){
        cerr<<"Non si puo' aprire il file!"<<endl;
        system("pause");
    }
   filista>>num;  
   while (!filista.eof()) { 
      bool temp=false;
      InsertSort2( Tree, num, temp); 
      if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
      else cout<<" Inserito numero= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

void InsertSort2( PAnodo &A,int m, bool &inserito)   { //OK
      if(A==NULL)  {
         A=new Anodo;
         A->key = m;
         A->left=NULL;
         A->right=NULL;
         inserito=true;
         }          
      else if(A->key<m)  InsertSort2(A->right,m,inserito);
      else if(A->key>m)  InsertSort2(A->left,m,inserito);
      else inserito=false;
}

Grazie 1000

[oregon]

Non funziona ? Errori ? Comportamenti anomali ? Fatto un po' di debug ?

[Skull260287]

Originariamente inviato da oregon
Non funziona ? Errori ? Comportamenti anomali ? Fatto un po' di debug ?

Come ho scritto nel primo post:

Non capisco perchè non funziona ad esempio quando vado a cancellare un nodo diverso dalla radice o per la radice stessa in alcuni casi.

Ho fatto debug ma sembra tutto ok nelle variabili e in ogni caso non sono riuscito a capire dove fallisce l'algoritmo.

[oregon]

Ho provato con un file di test e non ho avuto particolari problemi a cancellare i nodi ...

Se fornisci un esempio di file e un esempio di utilizzo in cui si puo' notare il comportamento anomalo, posso cercare di replicare il problema e trovarlo ...

[Skull260287]

Originariamente inviato da oregon
Ho provato con un file di test e non ho avuto particolari problemi a cancellare i nodi ...

Se fornisci un esempio di file e un esempio di utilizzo in cui si puo' notare il comportamento anomalo, posso cercare di replicare il problema e trovarlo ...

Genstilissimo, prova con questo file:

60	70	40	80	55	30	90	44	35	46	42	48	45	43	41

Prova a cancellare il nodo 44, a me non lo cancella.

[oregon]

Ho provato sia con VStudio 2003 che con DevCpp (e relativi compilatori) e funziona anche con il file che hai mostrato tu.

[Skull260287]

Originariamente inviato da oregon
Ho provato sia con VStudio 2003 che con DevCpp (e relativi compilatori) e funziona anche con il file che hai mostrato tu.

Bhà! Grazie mille, sei stato gentilissimo, ora mid evo scervellare per capire perchè a me non funziona.

[Skull260287]

All'interno di un programma più ampio che ha anche altri controlli e funzioni che lavorano sull'albero non va e non sono riuscito a capire perchè, per il resto funziona anche a me in un file a parte.