[C++]Problema Cancellazione Nodi BST (Albero Binario di Ricerca Ordinato)

[skull87]

Ho un problema su questo codice, la traccia la potete trovare in alto al codice stesso, praticamente l'algoritmo che calcola il numero di nodi indicati nella traccia mi sembra funzioni correttamente ma non ho capito per quale motivo i nodi indicati da cancellare non vengono cancellati. Il file albero.txt di partenza è 100 92 170 4 94 110 per entrambi gli alberi.

La funzione interessata è void AeB(PAnodo , PAnodo &,int &); e le sue collegate, il resto serve quasi per la maggior parte per effettuare una stampa grafica dell'albero.

Ecco il codice:

/*
Note : Sia A un albero qualsiasi e B un albero binario ordinato
Scrivere una procedura che calcoli quanti elementi
di B con almeno un figlio sono presenti in A, cancellando
contemporaneamente i nodi foglia di B presenti in A.

*/

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

#define TIPO_DATO int
#define OFFSET_SPACE 5

struct node {
int key;
struct node* left;
struct node* right;
};

struct node1{
TIPO_DATO *info; //Puntatore all'informazione tenuta dal nodo
struct node1 *left; //Puntatore sinistro
struct node1 *right; //Puntatore destro
};

struct elemCoda{
struct node1 *elem;
struct elemCoda *next;
};


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

typedef Albero *PAlbero;

using namespace std;

void StampaBST(PAlbero ,int );
void CreaAlberoDaFile(PAlbero &);
PAlbero AlberoCasualebst(int ); //Generazione Alberi Casuali Ord
void InsertSort2( PAlbero &,int , bool &);
void LegaPadre(PAlbero , PAlbero , PAlbero , PAlbero &);
void DelTNode(int , PAlbero &, bool &);
void NuovoCandidato(int , PAlbero &, PAlbero &);
void Cerca(PAlbero , int , PAlbero &, PAlbero &);
void DammiChiave(PAlbero ,int &);
void writeLevelTree(struct node1 *root); //Per Stampa Grafica
struct node1 *buildTree(); //Per Stampa Grafica
struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info); //Per Stampa Grafica
void pfileorder(PAlbero );
int Altezza(PAlbero );
void AeB(PAlbero , PAlbero &,int &);
void CercaNonno(PAlbero, int, PAlbero &,PAlbero &, PAlbero &);
bool cercaVal(PAlbero &,int);

int main(){

PAlbero A,B;
struct node1 *root = NULL;

CreaAlberoDaFile(A);
//StampaBST(A,0);
//system("pause");
//Crea albero
printf("\n\t\t .: 1 :. Costruzione albero...\n");
root = buildTree();
if (root==NULL) return 1;

//Stampa albero per livelli
system("cls");
writeLevelTree (root);
printf("\n\n\n");
system("pause");
//StampaBST(A,0);
CreaAlberoDaFile(B);
//B=AlberoCasualebst(3);

pfileorder(B);
//system("pause");
//Crea albero
printf("\n\t\t .: 1 :. Costruzione albero...\n");
root = buildTree();
if (root==NULL) return 1;

//Stampa albero per livelli
// system("cls");
writeLevelTree (root);
printf("\n\n\n");
cout<<endl;
cout<<endl;
system("pause");

int nodi=0;
AeB(A,B,nodi);

cout<<"Nodi: "<<nodi<<endl;

pfileorder(B);
//system("pause");
//Crea albero
printf("\n\t\t .: 1 :. Costruzione albero...\n");
root = buildTree();
if (root==NULL) return 1;

//Stampa albero per livelli
// system("cls");
writeLevelTree (root);
printf("\n\n\n");
cout<<endl;
cout<<endl;
system("pause");

system("pause");
return 0;

}

bool cercaVal(PAlbero &Tree, int val){
if(Tree==NULL)
return false;
else if(Tree->key==val && (Tree->left!=NULL || Tree->right!=NULL))
return true;
else if(Tree->key==val && Tree->left==NULL && Tree->right==NULL){
PAlbero Padre=NULL,Nonno=NULL;
CercaNonno(Tree,Tree->key,Tree,Padre,Nonno);
if(Padre!=NULL){
if(Padre->left!=NULL && Padre->left->key==val)
Padre->left=NULL;
else if(Padre->right!=NULL && Padre->right->key==val)
Padre->right=NULL;
}
return false;
}
else if(Tree->key>val)
return cercaVal(Tree->left,val);
else
return cercaVal(Tree->right,val);

}

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


int sommaNodi(PAlbero &Tree){
int k=0;
if(Tree!=NULL){
if(Tree->left!=NULL && Tree->right!=NULL) k=Tree->key;
else k=0; //non è una foglia
return sommaNodi(Tree->left)+sommaNodi(Tree->right)+k;
}
else
return 0;
}


void AeB(PAlbero A, PAlbero &B,int &nodi){
if(A!=NULL){
if(cercaVal(B,A->key)) nodi++;
AeB(A->left,B,nodi);
AeB(A->right,B,nodi);
}
}

//Generazione di albero BST ordinato
PAlbero Insertbst(int info1, PAlbero As, PAlbero Ad) {
// PER INSERIRE UNA FOGLIA SI CHIAMA CON Insert(Numero,NULL,NULL)
PAlbero A2;
A2= new Albero;
A2->key=info1;
if(As>Ad) swap(As,Ad);
A2->left=As;
A2->right=Ad;
return A2;
}

PAlbero AlberoCasualebst(int n)
{
//Dato un intero n restituisce un albero di interi di altezza n ORDINATO
if (n==0) {
//srand ( time(0) );
return Insertbst(rand()%100 ,NULL,NULL);
}
else{
//srand ( time(0) );
return Insertbst(rand()%100,AlberoCasualebst(n-1),AlberoCasualebst(n-1));
}
}

int Altezza(PAlbero A)
{ // CALCOLA L’ALTEZZA DELL’ALBERO A
int Hs, Hd;
if (A==NULL)
return -1;
else {
Hs=Altezza(A->left); Hd=Altezza(A->right);
if (Hs > Hd)
return ++Hs;
else
return ++Hd;
}
}


Continua...

[skull87]

void visita(PAlbero a, int livello, int i, ofstream &outlista) {

// Check Livello
if (i == livello) {
outlista<<a->key<<"\t";
return;
}
// Incrementa contatore livello
i++;
// Visita Nodo Sinistro
if (a->left != NULL)
visita(a->left, livello, i,outlista);
// Visita Nodo Destro
if (a->right != NULL)
visita(a->right, livello, i,outlista);
}

void pfileorder(PAlbero Tree){

int num;
//cout<<"Salva Albero su FILE:"<<endl;
string NomeLn,NomeOut;
ifstream filista;
ofstream outlista;
NomeOut="albero.txt";
outlista.open(NomeOut.c_str());
if(!outlista){
cerr<<"Non si puo' aprire il file!"<<endl;
system("pause");
}

for(int k=0;k<=Altezza(Tree);k++)
visita(Tree,k,0,outlista);

outlista.close();
}

//Function per la cancellazione di un nodo

void LegaPadre(PAlbero OldChild, PAlbero NewChild, PAlbero Padre, PAlbero &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, PAlbero &Candidato, PAlbero &Tree)
{ PAlbero Dummy; //variabile ausiliare per la chiamata a Cerca
PAlbero Padre; PAlbero 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(PAlbero Tree, int KeyValue, PAlbero &Node, PAlbero &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(PAlbero 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(PAlbero Candidato){

delete Candidato;
}

void DelTNode(int KeyValue, PAlbero &Tree, bool &Done)
{ PAlbero Candidato; // puntatore al nodo candidato per la cancellatura
PAlbero 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(PAlbero 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(PAlbero &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( PAlbero &A,int m, bool &inserito) { //OK
if(A==NULL) {
A=new Albero;
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;
}

/*
Helper function that allocates a new node
with the given data and NULL left and right
pointers.
*/
struct node* NewNode(int data) {
struct node* node = new(struct node); // "new" is like "malloc"
node->key = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/

struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(NewNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->key) node->left = insert(node->left, data);
else node->right = insert(node->right, data);

return(node); // return the (unchanged) node pointer
}
}


struct node1 *buildTree(){
/* int info;
struct node1 *root = NULL;

for(;info!=0;){
printf("\n\tInserire elementi (0 per terminare): ");
scanf("%d",&info);
if (info!=0){
printf("\tInserisco elemento %d nell'albero\n",info);
root = insertInOrder(root,info);
}
}
return root;*/
int num;
cout<<"Crea Albero da FILE:"<<endl;
struct node1 *root=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()){
root = insertInOrder(root,num);
filista>>num;
}
filista.close();
return root;
}

/* 2 */
/* 2.1 */
struct node1 *newNode(TIPO_DATO x){
struct node1 *elem = (struct node1 *)malloc (sizeof(struct node1));
TIPO_DATO *info = (TIPO_DATO *)malloc (sizeof(TIPO_DATO));

if ((elem==NULL)||(info==NULL)) return NULL;

*info = x;
elem->info = info;
elem->left = NULL;
elem->right = NULL;

return elem;
}

struct node1 *insertInOrder(struct node1 *root, TIPO_DATO info){
//Caso base
if (root == NULL) return (newNode(info));

//Ricorsione
if (info > *(root->info))
root->right = insertInOrder(root->right, info);
else
root->left = insertInOrder(root->left, info);
return root;
}

/* 5 */
/* 5.1 */
/* Restituisce il numero di livelli dell'albero */
/* (Necessario per una corretta spaziatura) */
int contaLivelli(struct node1 *root, int nLeft, int nRight){
int x,y;

if (root==NULL) return 0;
x = contaLivelli(root->left, nLeft+1, nRight);
y = contaLivelli(root->right, nLeft, nRight+1);

if (x>y) return (x+1);
return (y+1);
}

/* 5.2 */
/* Inserisce in coda alla lista puntata da "coda" il nodo x */
struct elemCoda *insertInTail(struct elemCoda *coda,struct node1 *x){
struct elemCoda *tmp = (struct elemCoda *) malloc (sizeof(struct elemCoda));
struct elemCoda *conta;

if (tmp==NULL) return NULL;
if (x==NULL){
tmp->elem = NULL;
tmp->next = NULL;
} else{
tmp->elem = x;
tmp->next = NULL;
}

if (coda==NULL) return tmp;

for(conta=coda;conta->next!=NULL;conta=conta->next);

conta->next = tmp;

return coda;
}


void writeLevelTree (struct node1 *root){
struct elemCoda *coda=NULL,
*tmp=NULL;
/* Per una "corretta" spaziatura */
int nLevel, //#livelli
nNodesCurrentLevel, //#nodi del livello correntemente elaborato
currentLevel=0, //#livello correntemente elaborato
conta, //var. per ciclo spaziatura
nCurrentNode=0; //#nodo correntemente in esame

//Calcolo numero livelli dell'albero
nLevel = contaLivelli(root,1,1); /* 5.1 */

//Inserimento radice albero in coda alla lista
coda = insertInTail(coda,root); /* 5.2 */

//Fin quando la coda dei nodi è piena...
for(;coda!=NULL;){

nNodesCurrentLevel=(int)pow (2, currentLevel); //#nodi del corrente livello (per spaziatura)
++nCurrentNode; //#nodo corrente rispetto al livello (per spaziatura)

//Spaziatura prima del valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");

//Valore del nodo (se il nodo non esiste, NULL, due spazi)
if (coda->elem!=NULL)
printf("%d",*(coda->elem->info));
else printf(" ");

//Spaziatura dopo il valore del nodo
for (conta=0; conta<(OFFSET_SPACE*nLevel/nNodesCurrentLevel); ++conta)
printf(" ");

//Se sono stati stampati tutti i nodi di questo livello
// vai a capo, azzera il #nodo corrente e incrementa
// il valore del livello corrente
if (nCurrentNode == nNodesCurrentLevel){
currentLevel++;
nCurrentNode=0;
//cout<<"\n L "<<currentLevel<<" \n";
printf("\n\n\n");
}

//Inserisci in coda i due figli (destro e sinistro) del nodo corrente.
tmp = coda;
coda = coda->next;
if (tmp->elem!=NULL){
coda = insertInTail(coda,tmp->elem->left);
coda = insertInTail(coda,tmp->elem->right);
} else
//Se il nodo corrente è NULL e questo in corso di elaborazione
// non è l'ultimo livello, inserisci in coda due figli NULL
// (destro e sinistro del nodo NULL) in coda (per una
// "corretta" spaziatura)
if (currentLevel<nLevel-1){
coda = insertInTail(coda,NULL);
coda = insertInTail(coda,NULL);
}
}
}



Grazie 1000.

[71104]

la traccia è posta male ed è implementata peggio: dalle definizioni delle struct all'inizio si vede che hai definito entrambi gli alberi come binari, mentre A è un albero generico, cioè un grafo connesso aciclico. inoltre hai implementato delle funzioni che prendono come primo parametro un puntatore ad un nodo: sono praticamente dei metodi.

[skull87]

la traccia è posta male ed è implementata peggio: dalle definizioni delle struct all'inizio si vede che hai definito entrambi gli alberi come binari, mentre A è un albero generico, cioè un grafo connesso aciclico. inoltre hai implementato delle funzioni che prendono come primo parametro un puntatore ad un nodo: sono praticamente dei metodi.

Per le funzioni che sono praticamente dei metodi ti riferisci a quelle commentate //Per stampa grafica?

Quelle non le ho scritte io, ho solo fatto in modo di far andare la mia struttura con quelle che mi stampano l'albero nella forma in cui lo disegneresti sul foglio.

Per quanto riguarda la struttura, la base è la stessa, ho pensato bene di semplificarmi la vita per una gestione migliore :-).

Cosa c'è da correggere per far andare il codice?

[71104]

Per le funzioni che sono praticamente dei metodi ti riferisci a quelle commentate //Per stampa grafica? tutte quelle che prendono in ingresso un parametro di tipo "PAnodo", "PAnodo&", o "struct nodo1*" : anziché come funzioni potevi implementarle come metodi delle struct Anodo e nodo1. è solo la prima semplificazione che si può fare nel tuo codice, quasi sicuramente se ne possono fare molte altre.

altra cosa: ti consiglierei di sceglierti uno straccio di naming convention coerente, e ti consiglierei di usare sempre nomi inglesi, perché quell' "Anodo" sembra una struct che descrive il contrario di un Catodo :D

[skull87]

altra cosa: ti consiglierei di sceglierti uno straccio di naming convention coerente, e ti consiglierei di usare sempre nomi inglesi, perché quell' "Anodo" sembra una struct che descrive il contrario di un Catodo :D

Eh....:-) me lo avevano già detto in effetti, solo che per velocizzarmi a trascrivere il codice sul pc non ho voluto fare la modifica, ma mi sa che lo faccio, anzi l'ho fatto: Albero va bene?

Ma sei riuscito a capire il problema per cui i nodi non mi vengono cancellati?

[DanieleC88]

quell' "Anodo" sembra una struct che descrive il contrario di un Catodo :D
Ma ROTFL! :rotfl:

[DanieleC88]

Sappi che non leggerò mai tutto quel codice alla ricerca dell'errore ( :D ), ti allego però un po' di roba che avevo scritto come esercizio in vista di un esonero, c'è anche un metodo abbastanza semplice per la cancellazione di un nodo da un albero binario di ricerca.

ciao ;)

[DanieleC88]

E giacché ci siamo, ma dal momento che scrivi questo programma in C++, perché usare printf() e compagnia bella? :)

[skull87]

Sappi che non leggerò mai tutto quel codice alla ricerca dell'errore ( :D ), ti allego però un po' di roba che avevo scritto come esercizio in vista di un esonero, c'è anche un metodo abbastanza semplice per la cancellazione di un nodo da un albero binario di ricerca.

ciao ;)

Grazie mille, le tue function possono sempre essre utili. ho risolto comunque, prendendo spunto dalla tua funzione. Il problema è che cancellavo il puntatore al padre, che è un puntatore ad un nodo dell'albero, ma il nodo dell'albero non veniva toccato, grazie mille.

[skull87]

E giacché ci siamo, ma dal momento che scrivi questo programma in C++, perché usare printf() e compagnia bella? :)

E...perchè le ho copiate da una persona che le ha scritte ed adattate al mio codice :-)