[C++] Determinare se un albero è sottoalbero di un altro.

[Skull260287]

La traccia dell'esercizio è questa:

Siano assegnati 2 alberi binari S e T; si determini se S è un sottoalbero di T oppure se T è un sottoalbero di S.

E' relativamente semplice e ho scritto il codice che vi posto. Il problema è che sto impazzendo per capire perchè la funzione cercaval non mi ritorna il valore del nodo Nodo.

Ho provato con questi due alberi:

T:
10 4 12 3 5 9 20

S:
5 9

Ecco il codice:

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


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

typedef Albero *PAlbero;

using namespace std;

int Altezza(PAlbero );
PAlbero Insert(int , PAlbero , PAlbero );
bool uguale(PAlbero , PAlbero );
bool CercaNodo(PAlbero,int,PAlbero &);
void CreaAlberoDaFile(PAlbero &);
void StampaBST(PAlbero ,int );
void InsertSort2( PAlbero &,int , bool &, bool &, bool &);
void confronto(PAlbero,PAlbero,int,int);

int main(){
    
    PAlbero T,S;
    CreaAlberoDaFile(T);
    CreaAlberoDaFile(S);
    int At=Altezza(T),As=Altezza(S);
    
    cout<<"Stampo T: "<<endl;    
    StampaBST(T,0);
    cout<<endl<<endl;
    cout<<"Stampo S: "<<endl;
    StampaBST(S,0);
    
    confronto(S,T,At,As);
    
    system("pause");
    return 0;
    
}

void confronto(PAlbero S,PAlbero T,int At,int As){
     
            if(At==As){     cout<<"Stessa Altezza"<<endl;
                            if(uguale(T,S)) cout<<"Si";
                            else cout<<"No"<<endl;
                            }
            else if(At<As){
                           cout<<"S altezza Maggiore di T"<<endl;
                           system("pause");
                           PAlbero Nodo;
                           CercaNodo(S,T->key,Nodo);
                           if(Nodo!=NULL && uguale(T,Nodo)) cout<<"Si";
                           else cout<<"No"<<endl;
                           }
            else {
                 cout<<"T altezza Maggiore di S"<<endl;
                 system("pause");
                 PAlbero Nodo=NULL;
                 cout<<"Chiave S"<<S->key<<endl;
                 system("pause");
                 CercaNodo(T,S->key,Nodo);
                 cout<<"Nodo Key"<<Nodo->key<<endl;
                 if(Nodo!=NULL && uguale(S,Nodo)) cout<<"Si";
                 else cout<<"No"<<endl;
                 }
            }

void StampaBST(PAlbero 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);
    }
}

bool CercaNodo(PAlbero Tree,int val,PAlbero &Nodo){
    
    if(Tree->key==val){
            Nodo=Tree;
            cout<<Nodo->key<<endl;
            system("pause");
            return true;
            }
    
    cout<<"Chiave Albero Ricerca: "<<Tree->key<<endl;
    system("pause");
    return CercaNodo(Tree->left,val,Nodo) &&  CercaNodo(Tree->right,val,Nodo);
}

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

void CreaAlberoDaFile(PAlbero &Tree){
    int num;
    cout<<"Crea Albero da FILE:"<<endl;
    system("pause");
    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;
      //bool left=false,right=false;
      //InsertSort2( Tree, num, temp,left,right);
      InsertSort2( Tree, num, temp); 
      if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
      else cout<<" Inserito numero= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

PAlbero Insert(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;
  A2->left=As;
  A2->right=Ad;
  return A2;
}

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

bool uguale(PAlbero A, PAlbero B)   
{ // VERIFICA SE DUE ALBERI SONO UGUALI

if (A==NULL || B==NULL)
  return (A==NULL) && (B==NULL);
    	// due alberi sono uguali se sono entrambi NULL
else
  return (A->key==B->key) && uguale(A->left,B->left) && uguale(A->right,B->right);
}


void InsertSort2( PAlbero &A,int m, bool &inserito, bool &left, bool &right)  
 { //Non Ord

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

Se qualcuno ha voglia di dare uno sguardo o nota subito il problema lo ringrazio.

[Skull260287]

Dovrei aver risolto così:

/*

   Note              : Siano assegnati 2 alberi binari S e T; si determini se S è 
                       un sottoalbero di T oppure se T è un sottoalbero di S. 
                       
                       Compito 16/01/08 Esercizio 3.

*/     

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


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

typedef Albero *PAlbero;

using namespace std;

int Altezza(PAlbero );
PAlbero Insert(int , PAlbero , PAlbero );
bool uguale(PAlbero , PAlbero );
void CercaNodo(PAlbero,int,PAlbero &);
void CreaAlberoDaFile(PAlbero &);
void StampaBST(PAlbero ,int );
void InsertSort2( PAlbero &,int , bool &, bool &, bool &);
void confronto(PAlbero,PAlbero,int,int,PAlbero &);

int main(){
    
    PAlbero T=NULL,S=NULL,Nodo=NULL;
    CreaAlberoDaFile(T);
    CreaAlberoDaFile(S);
    
    cout<<"Stampo T: "<<endl;    
    StampaBST(T,0);
    cout<<endl<<endl;
    cout<<"Stampo S: "<<endl;
    StampaBST(S,0);
    
    confronto(S,T,Altezza(T),Altezza(S),Nodo);
    
    system("pause");
    return 0;
    
}

void confronto(PAlbero S,PAlbero T,int At,int As,PAlbero &Nodo){
     
            if(At==As){     cout<<"Stessa Altezza"<<endl;
                            if(uguale(T,S)) cout<<"Si"<<endl;
                            else cout<<"No"<<endl;
                            }
            else if(At<As){
                           cout<<"S altezza Maggiore di T"<<endl;
                           //system("pause");
                           CercaNodo(S,T->key,Nodo);
                           //cout<<"Nodo Key "<<Nodo->key<<endl;
                          //system("pause");
                           if(Nodo!=NULL && uguale(T,Nodo)) cout<<"Si"<<endl;
                           else cout<<"No"<<endl;
                           }
            else {
                 cout<<"T altezza Maggiore di S"<<endl;
                 //system("pause");
                 cout<<"Chiave S"<<S->key<<endl;
                 //system("pause");
                 CercaNodo(T,S->key,Nodo);
                 //cout<<"Nodo Key "<<Nodo->key<<endl;
                 if(Nodo!=NULL && uguale(S,Nodo)) cout<<"Si"<<endl;
                 else cout<<"No"<<endl;
                 }
            }

void StampaBST(PAlbero 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);
    }
}

void CercaNodo(PAlbero Tree,int val,PAlbero &Nodo){
    
    if(Tree!=NULL){
                   if(Tree->key==val){
                                      Nodo=Tree;
                                      return;
                                      }

                   
                   CercaNodo(Tree->left,val,Nodo);
                   CercaNodo(Tree->right,val,Nodo);
                   }
}

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

void CreaAlberoDaFile(PAlbero &Tree){
    int num;
    cout<<"Crea Albero da FILE:"<<endl;
    system("pause");
    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;
      //bool left=false,right=false;
      //InsertSort2( Tree, num, temp,left,right); //Attivare per Casuale
      InsertSort2( Tree, num, temp); 
      if (temp==false) cout<<"Numero preesistente ="<<num<<endl;
      else cout<<" Inserito numero= "<<num<<endl;
      filista>>num;;
      }
      system("pause");
    filista.close();
}

PAlbero Insert(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;
  A2->left=As;
  A2->right=Ad;
  return A2;
}

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

bool uguale(PAlbero A, PAlbero B)   
{ // VERIFICA SE DUE ALBERI SONO UGUALI

if (A==NULL || B==NULL)
  return (A==NULL) && (B==NULL);
    	// due alberi sono uguali se sono entrambi NULL
else
  return (A->key==B->key) && uguale(A->left,B->left) && uguale(A->right,B->right);
}


void InsertSort2( PAlbero &A,int m, bool &inserito, bool &left, bool &right)  
 { //Non Ord

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

Grazie cmq