Arbori binari de cautare

    Arbori binari de cautare

Definitie: Se numeste arbore binar de cautare un arbore binar cu proprietatea ca toate elementele mai mici decat valoarea din nod se gasesc in subarborele stang, iar toate elementele mai mari decat valoarea asociata nodului se gasesc in subarborele drept.

Exemplu:
            6
        3       8
      1   4   7   9
      2   5
Observatie: Prin parcurgerea in inordine a unui arbore binar de cautare, se obtin informatiile atasate nodurilor in ordine crescatoare.
            Informatiile atasate nodurilor dintr-un arbore binar de cautare sunt distincte.
Crearea unui arbore binar de cautare:

    struct nod
                {
        tip_informatie inf;
        [int ap];
        nod *st,*dr;
                };
    nod *rad;

Crearea arborelui binar de cautare se face prin adaugarea repetata a cate unui nod intr-un arbore initial vid.

    void adauga(nod*&p,tip_informatie x)
    {
        if(p==NULL)
            {
            p = new nod;
            p->inf = x;
            [p->ap = 1];
            p->st=NULL;
            p->dr=NULL;
            }
        else
            {
            if(x>p->inf)
                adauga(p->dr,x);
            else
                if(x<p->inf)
                    adauga(p->st,x);
            [else p->ap++];
            }
    }

    void creare(nod*&p)
    {
    tip_inf x;
    for(int i=1;i<=n;i++)
    {
        cin >> x;
        adauga(p,x);
    }
    }
APEL: rad=NULL;
    creare(rad);

Aplicatie:
    Fisierul date.in contine numere intregi scrise pe una sau mai multe linii. Creati un arbore binar de cautare care va contine in fiecare nod fiecare valoare din fisier, impreuna cu numarul sau de aparitii. Afisati valoarea care apare de cele mai multe ori in fisier.

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("arbore.in");
struct nod
        {
        int inf;
        int ap;
        nod *st,*dr;
        };
nod *rad;
int maxx=0,nr=0;
void adauga(nod*&p,int x)
{
    if(p==NULL)
        {
        p = new nod;
        p->inf = x;
        p->ap = 1;
        p->st=NULL;
        p->dr=NULL;
        }
    else
        {
        if(x>p->inf)
            adauga(p->dr,x);
        else
            if(x<p->inf)
                adauga(p->st,x);
            else
                if(x==p->inf)
                    p->ap++;
        }
}
void creare(nod*&p)
{
    int x;
    f >> x;
    while(!f.eof())
    {
        adauga(p,x);
        f >> x;
    }
}
void afis(nod*p)
{
    if(p!=NULL)
    {
        afis(p->st);
        cout << p->inf << " apare de " << p->ap << " ori." <<endl;
        afis(p->dr);
    }
}
void maxim(nod*p)
{
    if(p!=NULL)
    {
    if(p->ap>maxx)
    {
        maxx=p->ap;
        nr=p->inf;
    }
    maxim(p->st);
    maxim(p->dr);
    }
}
void afismax(nod*p)
{
    if(p!=NULL)
    {
        if(p->ap==maxx)
             cout << p->inf << " ";
    afismax(p->st);
    afismax(p->dr);
    }
}
int main()
{
    rad=NULL;
    creare(rad);
    afis(rad);
    maxim(rad);
    cout << "Valorea maxima care a aparut in fisier este " << maxx << " si a aparut la nodurile: ";
    afismax(rad);
    return 0;
}


Aplicatie 2: Creati un arbore binar de cautare care va contine literele dintr-un cuvant, fara spatii intre ele. Afisati literele in ordine alfabetica si numarul de aparitii al fiecarei litere in sir dupa care creati o stiva care va contine vocalele din sirul dat. Afisati stiva obtinuta.

struct nods
        {
        tip_informatie inf;
        nods*ant;
        };
void adaugas(nods*&vf,tip_informatie x)
{
    if(vf==NULL)
        {
        vf = new nods;
        vf->inf=x;
        vf->ant=NULL;
        }
    else
        {
        nods*p;
        p = new nods;
        p->inf=x;
        p->ant=vf;
        vf=p;
        }
}

Rezolvare:
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
struct nods
        {
        char inf;
        nods*ant;
        };
struct nod
        {
        int inf;
        int ap;
        nod *st,*dr;
        };
nod*rad;
nods*vf;
ifstream f("vocale.in");
char voc[]="aeiouAEIOU";
void adaugas(nods*&vf,char x)
{
    if(vf==NULL)
        {
        vf = new nods;
        vf->inf=x;
        vf->ant=NULL;
        }
    else
        {
        nods*p;
        p = new nods;
        p->inf=x;
        p->ant=vf;
        vf=p;
        }
}
void adauga(nod*&p,char x)
{
    if(p==NULL)
        {
        p = new nod;
        p->inf = x;
        p->ap = 1;
        p->st=NULL;
        p->dr=NULL;
        }
    else
        {
        if(x>p->inf)
            adauga(p->dr,x);
        else
            if(x<p->inf)
                adauga(p->st,x);
            else
                if(x==p->inf)
                    p->ap++;
        }
}
void creare(nod*&p)
{
    char x;
    f >> x;
    while(!f.eof())
    {
        adauga(p,x);
        f >> x;
    }
}
void afis(nod*p)
{
    if(p!=NULL)
    {
        afis(p->st);
        cout << char(p->inf) << " apare de " << p->ap << " ori." <<endl;
        afis(p->dr);
    }
}
void crearestiva(nod*&p)
{
    if(p!=NULL)
    {
        crearestiva(p->st);
        if(strchr(voc,p->inf)!=NULL)
             adaugas(vf,p->inf);
        crearestiva(p->dr);
    }
}
void afis_s(nods*vf)
{
    nods*p;
    p=vf;
    while(p!=NULL)
    {
        cout << p->inf << " ";
        p=p->ant;
    }
}
int main()
{
    rad=NULL;
    vf=NULL;
    creare(rad);
    cout << "Literele in ordine alfabetica sunt: "<<endl;
    afis(rad);
    crearestiva(rad);
    cout << "Vocalele din sir sunt: ";
    afis_s(vf);
}