[C++] Approccio Algoritmico Per Affrontare Problemi Sugli Alberi

**Skull260287** · 04-06-2008, 14:05

Ciao a tutti, sto iniziando ad affrontare più in dettaglio l'approccio mentale e algoritmico per risolvere problemi riguardanti gli alberi Binari ordinati o meno. Vi propongo una traccia di un esercizio, io sono riuscito a fare le prime due funzioni, anche se le ho rese void nell'impotesi che ci potessero essere ripetizioni all'interno dell'albero, non sono riuscito a renderle char.

codice:

Descritte le parentele secondo un albero non ordinato scrivere le funzioni

char Padre
{dato un nome determinare se ha un padre e chi è}

void  Figlio
{dato un nome determinare se ha uno o  due figli e chi sono}

char Nonno  
 {dato un nome determinare chi è il nonno}

char Fratello
{dato un nome determinare se ha un fratello e chi è}
				
char Cugino
{dato un nome determinare se ha uno Cugino e chi è}

Il Mio Codice:

codice:

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <math.h>
#include <time.h> //Genera Numeri Casuali Tutti Diversi
#include <string>

struct Anodo{
             char key[20];
             Anodo *left,*right;
             };

typedef Anodo *PAnodo;


using namespace std;

void CreaAlberoDaFile(PAnodo &);
PAnodo InsertSort(char [],PAnodo );
void InsertSort2( PAnodo &,char [], bool &, bool &, bool &);
int Altezza(PAnodo );
void StampaBST(PAnodo ,int );
void pfileorder(PAnodo );

//Le Funzioni sono Void in quanto In un Albero Binario Non Ordinato Ci Possono
//Essere Ripetizioni
void padre(PAnodo ,char []);
void nonno(PAnodo ,char []);
void figli(PAnodo ,char [], int &);


int main(){
    
    PAnodo A;
    
    CreaAlberoDaFile(A);
    //A=AlberoCasuale(3);
    StampaBST(A,0);
    
    char dad[20];
    
  /*  cout<<"Inserisci Un Nome: ";
    cin>>dad;
    
   // char* son=
    padre(A,dad);
    //cout<<son;
    //system("pause");
    
   // if(son!="0") cout<<"Padre: "<<son<<endl;
   // else cout<<"Padre non trovato"<<endl;
   int nfigli=0;
   cout<<"Inserisci Un Nome: ";
   cin>>dad;
   
   figli(A,dad,nfigli);
   cout<<"\nNumero Figli: "<<nfigli<<endl;*/
   
   cout<<"Inserisci Un Nome: ";
   cin>>dad;
   
   nonno(A,dad);

    cout<<endl;
    
    system("pause");
    return 0;
    
}

void padre(PAnodo A,char Nome[]){
     
     if (A!=NULL){
                 padre(A->right,Nome); 
                 if(stricmp(A->left->key,Nome)==0 ||
                    stricmp(A->right->key,Nome)==0) 
                    cout<<"Padre: "<<A->key<<endl; 
                 padre(A->left,Nome);
                 
     }
     
}

void figli(PAnodo A,char Nome[],int &nfigli){
     
     if (A!=NULL){
                 figli(A->right,Nome,nfigli); 
                 if(stricmp(A->key,Nome)==0){
                 if(A->right!=NULL){
                                     nfigli++;
                                     cout<<"Figlio "<<nfigli<<" : ";
                                     cout<<A->right->key<<endl;
                                     }
                 if(A->left!=NULL){
                                     nfigli++;
                                     cout<<"Figlio "<<nfigli<<" : ";
                                     cout<<A->left->key<<endl;
                                     }
                 }
                                     
                 figli(A->left,Nome,nfigli);
                 
     }
     
}

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

/*
* Visita Ricorsivamente l'albero e salva i valori dei nodi che si trovano
* al livello specificato
*/


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){
     
    char num[20];
    //cout<<"Salva Albero su FILE:"<<endl;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeOut="alberocar.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 CreaAlberoDaFile(PAnodo &Tree){
    char num[20];
    cout<<"Crea Albero da FILE:"<<endl;
    Tree=NULL;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeLn="alberocar.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;
      bool left=false,right=false;
      InsertSort2( Tree, num, temp,left,right); 
      if (temp==false) cout<<"Nome preesistente ="<<num<<endl;
      else cout<<" Inserito Nome= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

//Essendo non Ordinato ci possono essere ripetizioni
void InsertSort2( PAnodo &A,char m[], bool &inserito, bool &left, bool &right)  
 { //Non Ord

       if(A==NULL)  {
         A=new Anodo;
         strcpy(A->key,m);
         A->left=NULL;
         A->right=NULL;
         inserito=true;
         }          
      else if(stricmp(A->key,m)<0 && !left){
                                       left=true;
                                       right=false;
                                       InsertSort2(A->right,m,inserito,left,right);
                                       
                                       }
      else if(stricmp(A->key,m)>0 && left && !right){
                                       left=false;
                                       right=true;
                                       InsertSort2(A->left,m,inserito,left,right);
                                       
                                       }
      else InsertSort2(A->left,m,inserito,left,right);
}

void StampaBST(PAnodo Tree,int i){
    if(Tree!=NULL){
        StampaBST(Tree->right,i+1);
        for(int j=1;j<=i;j++)
            cout<<"\t\t";
        cout<<Tree->key;
        cout<<endl<<endl<<endl;
        StampaBST(Tree->left,i+1);
    }
}

Grazie a tutti per l'aiuto che mi darete, non riesco ad entrare nell'ottica dell'albero, complice anche il caldo eccessivo di questi giorni ed altro...

**menphisx** · 04-06-2008, 14:32

Devi aggiungere un link al padre:

codice:

typedef struct Anodo{

   char key[20];
   Anodo *left,*right, *parent;

}Anodo;

Per la funzione figlio, controlla se nodo->left e nodo->right non sono null e ritornali.
Per la funzione padre, ritorna nodo->parent
Per la funzione fratello, ritorna nodo->parent->right (o left)
Per la funzione nonno, ritorna nodo->parent->parent
Per la funzione Cugino, ritorna nodo->parent->parent->left->left ( o right)

P.S.: cambia il nome da Anodo a qualcos'altro; Anodo sembra si riferisca ad un elettrodo

**Skull260287** · 04-06-2008, 19:38

Originariamente inviato da menphisx
Devi aggiungere un link al padre:

codice:

typedef struct Anodo{

   char key[20];
   Anodo *left,*right, *parent;

}Anodo;

Per la funzione figlio, controlla se nodo->left e nodo->right non sono null e ritornali.
Per la funzione padre, ritorna nodo->parent
Per la funzione fratello, ritorna nodo->parent->right (o left)
Per la funzione nonno, ritorna nodo->parent->parent
Per la funzione Cugino, ritorna nodo->parent->parent->left->left ( o right)

P.S.: cambia il nome da Anodo a qualcos'altro; Anodo sembra si riferisca ad un elettrodo

Grazie mille delle dritte, nei prossimi programmi cambierò il nome :-).

Per quanto riguarda il tuo consiglio di aggiungere il puntatore al padre, non ho capito come scrivere la funzione per la creazione dell'albero tenendo presente di questo nuovo puntatore, se mi posti un esempio te ne sarei grato.

Per ora ho scritto questo codice, mi sembra funzioni, ma mi sembra anche alquando "articolato". Mi rimetto ai vostri giudizi per apportare eventuali correzioni e modifiche, grazie mille.Ci ho messo un giorno intero ma forse qualcosa sto iniziando a capire, almeno lo spero.

codice:

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>

struct Anodo{
             char key[20];
             Anodo *left,*right;
             };

typedef Anodo *PAnodo;


using namespace std;

void CreaAlberoDaFile(PAnodo &);
PAnodo InsertSort(char [],PAnodo );
void InsertSort2( PAnodo &,char [], bool &, bool &, bool &);
int Altezza(PAnodo );
void StampaBST(PAnodo ,int );
void pfileorder(PAnodo );
PAnodo Insert(char [], PAnodo , PAnodo ); //Generazione Alberi Casuali NN Ord
PAnodo AlberoCasuale(int ); //Generazione Alberi Casuali NN Ord

//Le Funzioni sono Void in quanto In un Albero Binario Non Ordinato Ci Possono
//Essere Ripetizioni
void VisitaPadre(PAnodo ,int ,int ,char [],PAnodo &);
void VisitaFigli(PAnodo ,int ,int ,char [],PAnodo &,PAnodo &);
void VisitaFratello(PAnodo ,int ,int ,char [],PAnodo &);

int main(){
    
    PAnodo A,Padre=NULL,Figlio=NULL,Figlio1=NULL,Nonno=NULL,Fratello=NULL;
    PAnodo Padre1=NULL;
    
    CreaAlberoDaFile(A);
    //A=AlberoCasuale(4);
    StampaBST(A,0);
    system("pause");
    char dad[20];
    bool found=false;
     
    cout<<"Inserisci Un Nome: ";
    cin>>dad;
    //Se senza Ripetizioni mettere un while con un controllo che appena stampa
    //il padre trovato si ferma
    
    //Se ci sono ripetizioni ritorna l'ultimo trovato, per visualizzarli tutti
    //Inserire stampa all'interno delle function
    
    //Le Procedure si possono rendere comodamente funzioni inserendo i seguenti 
    //cicli for all'intero di una funziona char* con un return, ma in questo
    //Si esclude totalmente la possibilità di presenza di ripetizioni

   for(int i=0;i<Altezza(A);i++){
            VisitaPadre(A,0,i,dad,Padre);
            if(Padre!=NULL){ found=true; cout<<"Padre: "<<Padre->key<<endl;
            Padre=NULL;}
            }
            
    if (Padre==NULL && !found) cout<<"Nessun Padre"<<endl;

    cout<<endl;
    found=false;
    
    cout<<"Inserisci Un Nome: ";
    cin>>dad;
    
    for(int i=0;i<Altezza(A);i++){
            VisitaFigli(A,0,i,dad,Figlio,Figlio1);
            if(Figlio!=NULL){ found=true; cout<<"Figlio: "<<Figlio->key<<endl;
            Figlio=NULL;}
            if(Figlio1!=NULL){ found=true; cout<<"Figlio: "<<Figlio1->key<<endl;
            Figlio1=NULL;}
            }
            
    if (Figlio==NULL && Figlio1==NULL && !found) cout<<"Nessun Figlio"<<endl;

    cout<<endl;

    
    found=false;
    
    
    cout<<"Inserisci Un Nome: ";
    cin>>dad;
    
    //Non Funziona se ci sono ripetizioni
    //Ad esempio due nomi uguali al livello 2 e 3
    //O meglio ritorna il primo risultato che incontra
    for(int i=0;i<Altezza(A);i++){
            VisitaPadre(A,0,i,dad,Padre);
            if(Padre!=NULL){
            strcpy(Padre->key,dad);

            VisitaPadre(A,0,i-1,dad,Padre1);
            }

            if(Padre1!=NULL && !found && 
            stricmp(Padre1->key,dad)!=0)
            { found=true; cout<<"Nonno: "<<Padre1->key<<endl;
               Padre=NULL;}
            else Padre1==NULL;
            
            }
            
    if (Nonno==NULL && !found) cout<<"Nessun Nonno"<<endl;
    
   found=false;
     
    cout<<"Inserisci Un Nome: ";
    cin>>dad;

   for(int i=0;i<Altezza(A);i++){
            VisitaFratello(A,0,i,dad,Fratello);
            if(Fratello!=NULL){ found=true; cout<<"Fratello: "<<Fratello->key<<endl;
            Fratello=NULL;}
            
            }
            
    if (Fratello==NULL && !found) cout<<"Nessun Fratello"<<endl;

    cout<<endl;
    
    //Albero Senza Ripetizioni
    Figlio=NULL;
    Fratello=NULL;
    Figlio1=NULL;
    found=false;
    cout<<"Inserisci Un Nome: ";
    cin>>dad;
    
    char dad1[20];
    
    strcpy(dad1,dad);
    cout<<"\n"<<dad1<<endl;
    //system("pause");
    
    for(int i=0;i<Altezza(A);i++){
            
            VisitaPadre(A,0,i,dad,Padre);
            cout<<i<<endl;
            //system("pause");
            if(Padre!=NULL && i!=0){
            strcpy(dad,Padre->key);
            cout<<Padre->key<<endl;system("pause");
            VisitaPadre(A,0,i-1,dad,Padre1);
            }
            else if(Padre!=NULL && i==0){
                   if(Padre->left!=NULL && 
                   stricmp(Padre->left->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre->left->key<<endl;
                   found=true; 
                   }
              
                   if(Padre->right!=NULL && 
                   stricmp(Padre->right->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre->right->key<<endl;
                   found=true; 
                   }   
            }
            }
             if(Padre1!=NULL) cout<<Padre1->key<<endl;
             system("pause");

            if(Padre1!=NULL && !found)
            { 
              if(Padre1->left!=NULL && Padre1->left->left!=NULL && 
                   stricmp(Padre1->left->left->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre1->left->left->key<<endl;
                   found=true; 
                   }
              
              if(Padre1->left!=NULL && Padre1->left->right!=NULL && 
                   stricmp(Padre1->left->right->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre1->left->right->key<<endl;
                   found=true; 
                   }
              if(Padre1->right!=NULL && Padre1->right->left!=NULL && 
                   stricmp(Padre1->right->left->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre1->right->left->key<<endl;
                   found=true; 
                   }
              if(Padre1->right!=NULL && Padre1->right->right!=NULL && 
                   stricmp(Padre1->right->right->key,dad1)!=0){
                   cout<<"Cugino: "<<Padre1->right->right->key<<endl;
                   found=true; 
                   }
               Padre=NULL;
               }
            
            
    if (!found) cout<<"Nessun Cugino"<<endl;
    
    system("pause");
    return 0;
    
}

void VisitaFratello(PAnodo a,int i,int livello,char Nome[],PAnodo &Fratello){

      
       // Check Livello
        if (i == livello) {
              
        if(stricmp(a->left->key,Nome)==0 && a->right!=NULL)
        Fratello=a->right;
        else if(stricmp(a->right->key,Nome)==0 && a->left!=NULL)
        Fratello=a->left;
        //cout<<Padre->key;
        //system("pause");
        }
        // Incrementa contatore livello
        i++;
        // Visita Nodo Sinistro
        if (a->left != NULL)
        VisitaFratello(a->left, i,livello,Nome,Fratello);
        // Visita Nodo Destro
        if (a->right != NULL)
        VisitaFratello(a->right, i,livello,Nome,Fratello);
        }

void VisitaFigli(PAnodo a,int i,int livello,char Nome[],PAnodo &Figlio, PAnodo &Figlio1){

      
       // Check Livello
        if (i == livello) {
              
        if(stricmp(a->key,Nome)==0){
               if(a->left!=NULL) {Figlio=a->left; //cout<<Figlio->key<<endl;}
               if(a->right!=NULL) {Figlio1=a->right; //cout<<Figlio1->key<<endl;}
               }
        //cout<<Padre->key;
       // system("pause");
        }
        // Incrementa contatore livello
        i++;
        // Visita Nodo Sinistro
        if (a->left != NULL)
        VisitaFigli(a->left, i,livello,Nome,Figlio,Figlio1);
        // Visita Nodo Destro
        if (a->right != NULL)
        VisitaFigli(a->right, i,livello,Nome,Figlio,Figlio1);
        }}}

void VisitaPadre(PAnodo a,int i,int livello,char Nome[],PAnodo &Padre){

      
       // Check Livello
        if (i == livello) {
              
        if(stricmp(a->left->key,Nome)==0 ||
           stricmp(a->right->key,Nome)==0)
           
        Padre=a;
        //cout<<Padre->key;
        //system("pause");
        }
        // Incrementa contatore livello
        i++;
        // Visita Nodo Sinistro
        if (a->left != NULL)
        VisitaPadre(a->left, i,livello,Nome,Padre);
        // Visita Nodo Destro
        if (a->right != NULL)
        VisitaPadre(a->right, i,livello,Nome,Padre);
        }
      

PAnodo Insert(char info1[], PAnodo As, PAnodo Ad) {
// PER INSERIRE UNA FOGLIA SI CHIAMA CON Insert(Numero,NULL,NULL)                       
  PAnodo A2;
  A2= new Anodo;
  strcpy(A2->key,info1);
  A2->left=As;
  A2->right=Ad;
  return A2;
}

PAnodo AlberoCasuale(int n) {

    char *v[10]={
       "Marco",
       "Giulio",
       "Rocco",
       "Vincenzo",
       "Andrea",
       "Giulietta",
       "Alfa",
       "Romeo",
       "Domenico",
       "Francesco"
   };
   
   if (n==1)
      return Insert(v[rand() % 10], NULL, NULL);                            
   else
     return Insert(v[rand() % 10], AlberoCasuale(n-1), AlberoCasuale(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;
 }
}

/*
* Visita Ricorsivamente l'albero e salva i valori dei nodi che si trovano
* al livello specificato
*/


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){
     
    char num[20];
    //cout<<"Salva Albero su FILE:"<<endl;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeOut="alberocar.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();
}

Continua...

**Skull260287** · 04-06-2008, 19:42

...Continua

codice:


void CreaAlberoDaFile(PAnodo &Tree){
    char num[20];
    cout<<"Crea Albero da FILE:"<<endl;
    Tree=NULL;
    string NomeLn,NomeOut;
    ifstream filista;
    ofstream outlista;
    NomeLn="alberocar.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;
      bool left=false,right=false;
      InsertSort2( Tree, num, temp,left,right); 
      if (temp==false) cout<<"Nome preesistente ="<<num<<endl;
      else cout<<" Inserito Nome= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

//Essendo non Ordinato ci possono essere ripetizioni
void InsertSort2( PAnodo &A,char m[], bool &inserito, bool &left, bool &right)  
 { //Non Ord

       if(A==NULL)  {
         A=new Anodo;
         strcpy(A->key,m);
         A->left=NULL;
         A->right=NULL;
         inserito=true;
         }          
      else if(stricmp(A->key,m)<0 && !left){
                                       left=true;
                                       right=false;
                                       InsertSort2(A->right,m,inserito,left,right);
                                       
                                       }
      else if(stricmp(A->key,m)>0 && left && !right){
                                       left=false;
                                       right=true;
                                       InsertSort2(A->left,m,inserito,left,right);
                                       
                                       }
      else InsertSort2(A->left,m,inserito,left,right);
}
/*
void InsertSort3( PAnodo &A,char m[], bool &inserito)   { //Ordinato
      if(A==NULL)  {
         A=new Anodo;
         strcpy(A->key,m);
         A->left=NULL;
         A->right=NULL;
         inserito=true;
         }          
      else if(stricmp(A->key,m)<0)  InsertSort2(A->right,m,inserito);
      else if(stricmp(A->key,m)>0)  InsertSort2(A->left,m,inserito);
      else inserito=false;
}*/

void StampaBST(PAnodo Tree,int i){
    if(Tree!=NULL){
        StampaBST(Tree->right,i+1);
        for(int j=1;j<=i;j++)
            cout<<"\t\t";
        cout<<Tree->key;
        cout<<endl<<endl<<endl;
        StampaBST(Tree->left,i+1);
    }
}

Grazie

Discussione: [C++] Approccio Algoritmico Per Affrontare Problemi Sugli Alberi

Strumenti discussione

Ricerca discussione

Visualizza

[C++] Approccio Algoritmico Per Affrontare Problemi Sugli Alberi

Permessi di invio