Albero binario, ricerca, inserimento, cancellazione C++

Posted on at


Programma fatto con qt creator

file 1:

#include <iostream>
using namespace std;
#ifndef ABR_H
#define ABR_H
class nodo{
    int info_;
    nodo *des_;
    nodo *sin_;
public:
    nodo();
    nodo(const int &info);
    nodo *getDes();
    nodo *getSin();
    int getInfo();
    void setInfo(int &info);
    void setDes(nodo* des);
    void setSin(nodo* sin);
};
 
class abr
{
    nodo *head_;
    int size_=0;
 
public:
    abr();
    void aggiungiNodo(int info);
    void remove(int info);
    bool find(int info);
    void visita(nodo *p);
    nodo *gethead();
    bool isEmpty();
    int size();
    int decsize();
    int printSize();
    int ordvet(int vet[]);
    int printAlbero(int vet[]);
};
 
#endif // ABR_H


file 2:

#include "abr.h"
#include <iostream>
using namespace std;
nodo::nodo(const int &info){
    info_=info;
    des_=0;
    sin_=0;
}
 
void nodo::setSin(nodo *sin){
    sin_=sin;
 
}
void nodo::setDes(nodo *des){
    des_=des;
 
}
 
 
void nodo::setInfo(int &info){
    info_=info;
}
int nodo::getInfo(){
    return info_;
}
nodo* nodo::getDes(){
    return des_;
 
}
nodo* nodo::getSin(){
    return sin_;
}
 
abr::abr()
{
    head_=0;
}
 
 
void abr::aggiungiNodo(int info){
    nodo *n = new nodo(info);
    nodo *Corr,*Prec;
    if(head_==0)
        head_=n;
    else{
        Prec=head_;
        if(info<Prec->getInfo())
            Corr=Prec->getSin();
        else
            Corr=Prec->getDes();
        while(Corr!=0){
            Prec=Corr;
        if(info<Prec->getInfo())
            Corr=Prec->getSin();
        else
            Corr=Prec->getDes();
    }
        if(info<Prec->getInfo())
            Prec->setSin(n);
        else
            Prec->setDes(n);
    }
    size();
}
 
 
void abr::visita(nodo *p){
    if(p==0)
        cout<<p->getInfo()<<"  ";
    else{
    if(p->getSin()!=0)
        visita(p->getSin());
    cout<<p->getInfo()<<"  ";
    if(p->getDes()!=0)
        visita(p->getDes());
}}
nodo* abr::gethead(){
    return head_;
}
bool abr::find(int info){
    nodo *p=head_;
    while(p!=0){
        if(p->getInfo()==info)
            return true;
        if(p->getInfo()>info)
            p=p->getSin();
        else p=p->getDes();
    }
return false;
}
bool abr::isEmpty(){
    if(head_==0)
        return true;
    return false;
}
 
int abr::size(){
    size_++;
}
 
int abr::decsize(){
    size_--;
}
 
int abr::printSize(){
    return size_;
}
 
int abr::ordvet(int vet[]){
    int app;
    for(int i=0;i<printSize();i++){
        for(int j=0;j<printSize();j++){
            if(j!= (printSize()-1) && vet[j]>vet[j+1]){
                app= vet[j];
                vet[j]=vet[j+1];
                vet[j+1]=app;
            }
        }
    }
}
 
int abr::printAlbero(int vet[]){
    if(printSize()==1)
        cout<<"              "<<vet[0]<<endl;
    if(printSize()==2)
        cout<<"              "<<vet[0]<<endl<<"                 "<<vet[1]<<endl;
    if(printSize()==3)
        cout<<"              "<<vet[1]<<endl<<"           "<<vet[0]<<"     "<<vet[2]<<endl;
    if(printSize()==4)
        cout<<"              "<<vet[1]<<endl<<"           "<<vet[0]<<"     "<<vet[2]<<endl<<"                   "<<vet[3]<<endl;
    if(printSize()==5)
        cout<<"              "<<vet[1]<<endl<<"           "<<vet[0]<<"     "<<vet[3]<<endl<<"               "<<vet[2]<<"   "<<vet[4]<<endl;
    if(printSize()==6)
        cout<<"              "<<vet[2]<<endl<<"           "<<vet[0]<<"     "<<vet[4]<<endl<<"            "<<vet[1]<<"   "<<vet[3]<<" "<<vet[5]<<endl;
    if(printSize()==7)
        cout<<"              "<<vet[3]<<endl<<"           "<<vet[1]<<"     "<<vet[5]<<endl<<"          "<<vet[0]<<" "<<vet[2]<<"   "<<vet[4]<<" "<<vet[6]<<endl;
}
 
 
file 3:

#include <abr.h>
#include <iostream>
#include <cstdlib>
 
using namespace std;
int main()
{
    nodo *head;
    abr albero;
    int info;
    int ele;
    int scelta,i=0;
    int vet[100];
    do{
 
        system("CLS");
    cout<<"\tMenu"<<endl;
    cout<<"1.Inserzione"<<endl;
    cout<<"2.Ricerca"<<endl;
    cout<<"3.Cancellazione"<<endl;
    cout<<"4.Stampa ordinata"<<endl;
    cout<<"5.stampa albero"<<endl;
    cout<<"6.Stampa numero elementi"<<endl;
    cout<<"7.Stampa altezza"<<endl;
    cout<<"0.Uscire"<<endl;
    cout<<"Scelta: ";
    cin>>scelta;
    switch(scelta){
    case 1:
        cout<<"Inserisci il nuovo nodo : ";
        cin>>info;
        vet[i]=info;
        albero.aggiungiNodo(info);
        i++;
        albero.ordvet(vet);
        break;
    case 2:
        if(albero.isEmpty()==true){
            cout<<"ERRORE!!! devi inserire prima la radice"<<endl;
 
        }
        else{
            cout<<"Numero da cercare nell'albero: ";
            cin>>info;
            if(albero.find(info)==true)
                cout<<"elemento trovato"<<endl;
            else
                cout<<"elemento non trovato"<<endl;
        }
        break;
    case 3:
        cout<<"Inserisci l' elemento da eliminare: ";
        cin>>ele;
        for(int j=0;j<albero.printSize();j++)
            if(vet[j]==ele)
                for(j=j;j<(albero.printSize()-1);j++)
                    vet[j]=vet[j+1];
        albero.decsize();
        break;
    case 4:
        if(albero.isEmpty()==true){
            cout<<"ERRORE!!! devi inserire prima la radice"<<endl;
 
        }
        else{
        head=albero.gethead();
        cout<<"\nStampa ordinata: ";
        albero.visita(head);
        cout<<endl;
        }
        break;
    case 5:
        albero.printAlbero(vet);
        break;
    case 6:
        cout<<"L' albero ha "<<albero.printSize()<<" elementi"<<endl;
    case 7:
        if(albero.printSize()== 1 && albero.printSize() == 0)
            cout<<"L'altezza e' 0"<<endl;
        if(albero.printSize()== 2 && albero.printSize() == 3)
            cout<<"L'altezza e' 1"<<endl;
        if(albero.printSize()>3 && albero.printSize()<=7 )
            cout<<"L'altezza e' 2"<<endl;
        if(albero.printSize()>7 && albero.printSize()<=15)
            cout<<"L'altezza e' 3"<<endl;
        if(albero.printSize()>15 && albero.printSize()<=31)
            cout<<"L'altezza e' 4"<<endl;
        if(albero.printSize()>31 && albero.printSize()<=63)
            cout<<"L'altezza e' 5"<<endl;
            break;
    default:
        cout<<"Arrivederci"<<endl;
        break;
}
    system("pause");
 
    }while(scelta!=0);
 
 
    return 0;
}
 


About the author

darkrei

cool filmannex user

Subscribe 0
160