[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:

Codice PHP:

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

Codice PHP:

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]

Originariamente inviato da 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.

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]

Originariamente inviato da skull87

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

[skull87]

Originariamente inviato da 71104

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

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]

Originariamente inviato da 71104

quell' "Anodo" sembra una struct che descrive il contrario di un Catodo

Ma ROTFL!

[DanieleC88]

Sappi che non leggerò mai tutto quel codice alla ricerca dell'errore ( ), 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]

Originariamente inviato da DanieleC88

Sappi che non leggerò mai tutto quel codice alla ricerca dell'errore ( ), 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]

Originariamente inviato da DanieleC88

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 :-)