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

[Skull260287]

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]

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]

Risolto grazie allo spunto avuto qui: http://www.hwupgrade.it/forum/showthread.php?t=1765960


Grazie a tutti in ogni caso.