Arbori binari de căutare

  • Propunere 1: Să se scrie o structură de date eficientă pentru lucrul cu arborii binari (conţinând în noduri numere întregi).
  • Propunere 2: Să se proiecteze o aplicaţie simplă care să prelucreze arborii binari

Proprietate

Fiecare nod conţine un element care este mai mare decât elementul din oricare nod al subarborelui stâng (daca există) şi mai mic sau egal cu orice element din subarborele drept (dacă există).

Adăugarea recursivă a unui nou element într-un arbore binar de căutare

  • dacă arborele este NULL, atunci se creează un nod în care se pune acest element;
  • dacă arborele nu este NULL, atunci:
    • dacă elementul din rădăcină este > elementul nou sosit, acesta se adaugă în subarborele din stângă;
    • dacă nu, el se adaugă în subarborele din dreapta.

Declarare arbori binari (de căutare)

typedef int tipDate;
struct nod {
    tipDate info;
    struct nod *st; struct nod *dr;
};
typedef nod * arbore;

Arbori binari de căutare – inițializare

int esteArboreNul(arbore a)
{ 
   return (a==NULL); 
}

void initArbore(arbore& a) 
{ 
   if (!esteArboreNul(a)) a=NULL; 
}

Adăugarea unui element într-un arbore binar de căutare

bool adaugaLaArboreElement(arbore& a, tipDate el) {
    if (esteArboreNul(a)) {
        a=new nod;
        if (!a) return false;
        a->info = el; a->st = NULL; a->dr = NULL;
        return true;
    }
    else if (el < a->info)
        return adaugaLaArboreElement(a->st, el);
    else
        return adaugaLaArboreElement(a->dr, el);
}

Căutarea unui element în acest arbore

bool existaElementInArbore(arbore a, tipDate el)
{
    if (!esteArboreNul(a)) // sau if (a)
    {
        if (a->info==el) return true;
        else 
          if (el<a->info) 
             return existaElementInArbore(a->st, el);
          else 
             return existaElementInArbore(a->dr, el);
    }
    else
        return false;
}

Parcurgerea arborilor binari

Preordine:  rădăcina, subarborele stând, subarborele drept

void parcurgereInPreordine(arbore a)
{
    if (!esteArboreNul(a))
    {
        cout<<a->info<<", ";
        parcurgereInPreordine(a->st);
        parcurgereInPreordine(a->dr);
    }
}

Postordine:  subarborele stând, subarborele drept, rădăcina

void parcurgereInPostordine(arbore a)
{
    if (!esteArboreNul(a))
    {
        parcurgereInPostordine(a->st);
        parcurgereInPostordine(a->dr);
        cout<<a->info<<", ";
    }
}

Inordine: subarborele stâng, rădăcina, subarborele drept

void parcurgereInInordine(arbore a)
{
    if (!esteArboreNul(a))
    {
        parcurgereInInordine(a->st);
        cout<<a->info<<", ";
        parcurgereInInordine(a->dr);
    }
}

Un program demonstrativ

int main() {
    cout << "Arbori binari de cautare\n\n";
    arbore a; initArbore(a);
    unsigned int i; unsigned int n;
    tipDate x;
    cout<<"Dati numarul de elemente ale arborelui: "; cin>>n;
    for (i=1; i<=n; i++) {
        cout<<"Dati elementul al "<<i<<"-lea: ";
        cin>>x; adaugaLaArboreElement(a,x); 
    }
    cout<<"\nElementele parcurse in inordine sunt ordonate crescator:\n";
    parcurgereInInordine(a);
    return 0; 
}

Execuția programului

Grafuri

  • Notiuni elementare
  • Reprezentare
  • Algoritmul lui Prim

Proprietate

Un graf (neorientat sau orientat) este o pereche ordonată de mulţimi G=(V,E).
Mulţimea V este o mulţime nevidă şi finită de elemente denumite vârfurile/nodurile grafului.
Mulţimea E este o mulţime de perechi de vârfuri din graf.
În cazul grafurilor neorientate, perechile de vârfuri din mulţimea E sunt neordonate şi sunt denumite muchii. Perechea neordonată formată din vârfurile x şi y se notează [x,y]; vârfurile x şi y se numesc extremităţile muchiei [x,y].
În cazul grafurilor orientate, perechile de vârfuri din mulţimea E sunt ordonate şi sunt denumite arce.
Dacă există un arc sau o muchie cu extremităţile x şi y, atunci vârfurile x şi y sunt adiacente; fiecare extremitate a unei muchii/unui arc este considerată incidentă cu muchia/arcul respectiv.
Vom considera că extremităţile unei muchii, respectiv ale unui arc, sunt distincte (adică graful nu conţine bucle).

Reprezentare vizuala

Matrice de adiacenta

Fie G=(V,E) un graf neorientat, cu n varfuri si m muchii. Matricea de adiacenta asociata grafului G este o matrice patratica de ordinul n, cu n elemente, definite astfel:

Exemple de implementare:

int a[100][100];
.................................
cout<<"n="; cin>>n;
//se citesc valorile elementelor de deasupra diagonalei principale
for (i=1;i<=n-l;i++)
 for (j=i+l; j<=n; j++) { 
   cin>>a[i][j]; 
   //si se transferă si sub diagonala principală
   a[j][i]=a[i][j];
}
..............................
cin>>n; //numarul de noduri
cin>>m; //numarul de muchii
for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
    a[i][j]=0;
for (i=1;i<=m;i++)
{
  cout<<"dati extremitatile muchiei "<<i; 
  cin>>x >>y;
  a[x][y]=1;
  a[y][x]= 1;
}

Liste de adiacenta

Reprezentarea grafului G prin liste de adiacentă constă în:

  • precizarea numărului de vârfuri, n;
  • pentru fiecare vârf i, se precizează lista Li a vecinilor săi, adică lista nodurilor adiacente cu nodul i.

Exemplu de implementare:

typedef struct nod{
	int inf;
	nod *urm;
}AD;
AD *L[N];  //listele vecinilor
void citire()
{
	int i,j,k; 
        AD *x;
	cin>>n; //numarul de varfuri
        cin>>m; //numarul de muchii
        //aloca adrese pentru listele vecinilor 
	for(i=1;i<=n;i++) {
          L[i]=new AD; 
          L[i]->urm=NULL;
	}
	for (k=1;k<=m;k++)
	{	
          cin>>i>>j;
	  //adaug j in lista vecinilor lui i
	  x=new AD; x->inf=j; x->urm=L[i]->urm; L[i]->urm=x;  
	  //adaug i in lista vecinilor lui j
	  x=new AD; x->inf=i; x->urm=L[j]->urm; L[j]->urm=x;  	
	}
}