PDA

Visualizza la versione completa : [C++]Problema Cancellazione Nodi BST (Albero Binario di Ricerca Ordinato)


Skull260287
16-06-2008, 19:49
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 Anodo{
int key;
Anodo *left,*right;
};

typedef Anodo *PAnodo;

using namespace std;

void StampaBST(PAnodo ,int );
void CreaAlberoDaFile(PAnodo &);
PAnodo AlberoCasualebst(int ); //Generazione Alberi Casuali Ord
void InsertSort2( PAnodo &,int , bool &);
void DammiChiave(PAnodo ,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(PAnodo );
int Altezza(PAnodo );
void AeB(PAnodo , PAnodo &,int &);
void CercaNonno(PAnodo, int, PAnodo &,PAnodo &, PAnodo &);
bool cercaVal(PAnodo &,int);

int main(){

PAnodo 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(PAnodo &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){
PAnodo 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(PAnodo Tree, int KeyValue, PAnodo &Node,PAnodo &Padre, PAnodo &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(PAnodo &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(PAnodo A, PAnodo &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
PAnodo Insertbst(int info1, PAnodo As, PAnodo Ad) {
// PER INSERIRE UNA FOGLIA SI CHIAMA CON Insert(Numero,NULL,NULL)
PAnodo A2;
A2= new Anodo;
A2->key=info1;
if(As>Ad) swap(As,Ad);
A2->left=As;
A2->right=Ad;
return A2;
}

PAnodo 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(PAnodo 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;
}
}

Skull260287
16-06-2008, 19:50
void visita(PAnodo 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(PAnodo 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();
}

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 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;
}

/*
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.

Skull260287
19-06-2008, 16:02
Risolto grazie allo spunto avuto qui: http://www.hwupgrade.it/forum/showthread.php?t=1765960


Grazie a tutti in ogni caso.

Loading