PDA

Visualizza la versione completa : [C++] Cancellazione nodi da Alberi Binari, non capisco percè non funziona


Skull260287
31-05-2008, 16:20
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
31-05-2008, 17:03
Non funziona ? Errori ? Comportamenti anomali ? Fatto un po' di debug ?

Skull260287
31-05-2008, 18:58
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
31-05-2008, 19:06
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
31-05-2008, 22:59
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
01-06-2008, 07:45
Ho provato sia con VStudio 2003 che con DevCpp (e relativi compilatori) e funziona anche con il file che hai mostrato tu.

Skull260287
01-06-2008, 07:59
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
01-06-2008, 08:13
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.

Loading