Arbori binari

Arborii binari sunt arbori în care nodurile conţin cel mult doi descendenţi. Pentru memorarea acestor arbori se poate folosi o structură mai simplă de forma:

// tipul de date al informatiilor utile

typedef double TipArbore;

// structura care reprezinta un nod

// dintr-un arbore binar

struct NodArbore

{

// informatiile utile stocate in nod

TipArbore Informatii;

// vector de legaturi catre fii

NodArbore *Stanga, *Dreapta;

};

Operaţiile sunt aceleaşi ca şi în cazul arborilor oarecare.

Exemplu: parcurgerea arborelui în ordinea stânga – rădăcină - dreapta şi stocarea elementelor într-o listă:

// nodul listei simplu inlantuite

struct NodLista

{

// informatia utila

TipArbore Informatii;

// legastura catre elementul urmator

NodLista *Legatura;

// constructorul pentru initializarea unui nod

NodLista(TipArbore info, NodLista* leg = NULL)

: Informatii(info), Legatura(leg) {}

};

// functie de concatenare a doua liste simplu inlantuite

NodLista* Concatenare(NodLista *cap1, NodLista *cap2)

{

// cazul 1: prima lista e vida

if (cap1 == NULL)

return cap2;

// cazul 2: prima lista e nevida

// parcurgem prima lista

while (cap1->Legatura != NULL)

cap1 = cap1->Legatura;

// si facem legatura

cap1->Legatura = cap2;

// intoarcem capul listei

return cap1;

}

// procedura recursiva de parcurgere a unui arbore binar

NodLista* Parcurgere(NodArbore *nod)

{

// conditia de oprire din recursie

if (nod == NULL)

return NULL;

// initializam lista

NodLista *cap = NULL;

// adaugam subarborele stang

cap = Concatenare(cap, Parcurgere(nod->Stanga));

// adaugam nodul curent

cap = Concatenare(cap, new NodLista(nod->Informatii));

// adaugam subarborele drept

cap = Concatenare(cap, Parcurgere(nod->Dreapta));

return cap;

}

Arborii oarecare pot fi memoraţi ca arbori binari schimbând semantica legăturilor nodului astfel:

· legătura stânga va adresa primul fiu

· legătura dreapta va adresa următorul frate

Exemplu de transformare:

a) arbore oarecare:

b) arbore oarecare memorat ca arbore binar:

Arbori binari de căutare

Arborii binari de căutare sunt arbori binari în care nodurile sunt memorate ordonat în funcţie de o cheie. Toate nodurile din arbore au în subarborele stâng noduri care au chei mai mici şi în subarborele drept chei mai mari.

Arborii de căutare permit regăsirea rapidă a informaţiilor (O(log₂ n)) atât timp cât arborele este echilibrat. În cazul cel mai defavorabil, timpul de căutare este identic cu cel al unei liste simplu înlănţuite.

Operaţiile de bază pe un arbore de căutare sunt următoarele:

Implementarea operaţiilor de bază este prezentată în următoarea bibliotecă:

#ifndef ARBORE_H

#define ARBORE_H

// un nod din arbore

struct NodArbore

{

// informatia utila

TipArbore Date;

// legaturile catre subarbori

NodArbore *Stanga, *Dreapta;

// constructor pentru initializarea unui nod nou

NodArbore(TipArbore date,

NodArbore *stanga = NULL, NodArbore *dreapta = NULL) :

Date(date), Stanga(stanga), Dreapta(dreapta){}

};

// Arborele este manipulat sub

// forma unui pointer catre radacina

typedef NodArbore* Arbore;

// Creaza un arbore vid

Arbore ArbCreare()

{

return NULL;

}

// Testeaza daca un arbore este vid

bool ArbEGol(Arbore& arbore)

{

return arbore == NULL;

}

// Adauga un element intr-un arbore de cautare

void ArbAdauga(Arbore& arbore, TipArbore date)

{

// Cazul 1: arbore vid

if (ArbEGol(arbore))

{

arbore = new NodArbore(date);

return;

}

// Cazul 2: arbore nevid

if (date < arbore->Date)

// daca exista subarborele stang

if (arbore->Stanga != NULL)

// inseram in subarbore

ArbAdauga(arbore->Stanga, date);

else

// cream subarborele stang

arbore->Stanga = new NodArbore(date);

if (date > arbore->Date)

// daca exista subarborele drept

if (arbore->Dreapta != NULL)

// inseram in subarbore

ArbAdauga(arbore->Dreapta, date);

else

// cream subarborele drept

arbore->Dreapta = new NodArbore(date);

}

// Functie privata de stergere a unui nod

void __ArbStergeNod(Arbore& legParinte)

{

// salvam un pointer la nodul de sters

Arbore nod = legParinte;

// daca avem un subarbore drept

if (nod->Dreapta != NULL)

{

// facem legatura

legParinte = nod->Dreapta;

// daca avem si un subarbore stang

if (nod->Stanga)

{

// cautam cel mai mic element din subarborele drept

Arbore temp = nod->Dreapta;

while (temp->Stanga != NULL)

temp = temp->Stanga;

// si adaugam subarborele stang

temp->Stanga = nod->Stanga;

}

}

else

// daca avem doar un subarbore stang

if (nod->Stanga != NULL)

// facem legatura la acesta

legParinte = nod->Stanga;

else

// daca nu avem nici un subnod

legParinte = NULL;

// stergem nodul

delete nod;

}

// Sterge un nod dintr-un arbore de cautare

void ArbSterge(Arbore& arbore, TipArbore date)

{

// Cazul 1: arbore vid

if (ArbEGol(arbore))

return;

// Cazul 2: stergere radacina

if (arbore->Date == date)

{

// salvam un pointer la radacina

Arbore nod = arbore;

// daca avem un subarbore drept

if (nod->Dreapta)

{

// facem legatura

arbore = nod->Dreapta;

// daca avem si un subarbore stang

if (nod->Stanga)

{

// cautam cel mai mic element din subarborele drept

Arbore temp = nod->Dreapta;

while (temp->Stanga != NULL)

temp = temp->Stanga;

// si adaugam subarborele stang

temp->Stanga = nod->Stanga;

}

}

else

// daca avem doar un subarbore stang

if (nod->Stanga != NULL)

// facem legatura la acesta

arbore = nod->Stanga;

else

// daca nu avem nici un subnod

arbore = NULL;

// stergem vechea radacina

delete nod;

return;

}

// Cazul 3: stergere nod in arbore nevid

// cautam legatura la nod in arbore

// si stergem nodul (daca exista)

Arbore nodCurent = arbore;

while (true)

{

if (date < nodCurent->Date)

if (nodCurent->Stanga == NULL)

break; // nodul nu exista

else

if (nodCurent->Stanga->Date == date)

// nodul de sters este descendentul stang

__ArbStergeNod(nodCurent->Stanga);

else

// continuam cautarea in subarborele stang

nodCurent = nodCurent->Stanga;

else

if (nodCurent->Dreapta == NULL)

break; // nodul nu exista

else

if (nodCurent->Dreapta->Date == date)

// nodul de sters este descendentul drept

__ArbStergeNod(nodCurent->Dreapta);

else

// continuam cautarea in subarborele stang

nodCurent = nodCurent->Dreapta;

}

}

// Cauta recursiv un nod in arborele de cautare

bool Cautare(Arbore& arbore, TipArbore info)

{

// conditia de oprire din recursie

if (arbore == NULL)

return false;

// verificam daca am gasit nodul

if (arbore->Date == info)

return true;

// daca cheia este mai mica

if (arbore->Date < info)

// cautam in subarborele stang

return Cautare(arbore->Stanga, info);

else

// altfel cautam in subarborele drept

return Cautare(arbore->Dreapta, info);

}

#endif //ARBORE_H

Parcurgerea unui arbore de căutare în ordinea stânga – rădăcină – dreapta conduce la obţinerea listei nodurilor în ordinea crescătoare a cheilor. Funcţia următoare afişează în ordine elementele unui arbore binar de căutare:

void AfisareSRD(Arbore& arbore)

{

if (ArbEGol(arbore))

return;

AfisareSRD(arbore->Stanga);

cout << arbore->Date << " ";

AfisareSRD(arbore->Dreapta);

}

Parcurgerea nerecursivă a unui arbore binar de căutare se poate face folosind o stivă:

void TraversareNerecursiv(Arbore& arbore)

{

Stiva stiva = StCreare();

// a) ne deplasam pana la primul nod

Arbore nod = arbore;

while (nod != NULL)

{

StAdauga(stiva, nod);

nod = nod->Stanga;

}

if (!StEGoala(stiva))

cout << StVarf(stiva)->Date << " ";

// b) traversam arborele in inordine

Arbore parinte, copil;

while (!StEGoala(stiva))

{

parinte = StExtrage(stiva);

copil = parinte->Dreapta;

while (copil != NULL)

{

StAdauga(stiva, copil);

copil = copil->Stanga;

}

if (!StEGoala(stiva))

cout << StVarf(stiva)->Date << " ";

}

}