Arborii sunt structuri de date dinamice şi omogene. Cele mai comune utilizări ale arborilor sunt căutarea în volume mari de date şi reprezentarea de structuri organizate ierarhic.

1. Arbori oarecare

Arborii oarecare sunt colecţii de noduri care conţin informaţia utilă şi legături către descendenţi. Fiecare arbore conţine un nod iniţial numit rădăcină.

Structura unui arbore oarecare este prezentată în figura următoare:

Pentru implementarea unui arbore oarecare în C/C++ se poate folosi o structură de forma:

// tipul de date al informatiilor utile

typedef double TipArbore;

// structura care reprezinta un nod din arbore

struct NodArbore

{

// informatiile utile stocate in nod

TipArbore Informatii;

// numarul de legaturi catre fii

int numarLegaturi;

// vector de legaturi catre fii

NodArbore **Legaturi;

};

Fiecare nod conţine informaţiile utile, un întreg care reţine numărul de fii şi un vector de pointeri către fii.

Principalele operaţii care pot fi implementate pe un arbore oarecare sunt:

Exemplu de operaţie – ştergerea unui nod:

// sterge un nod din arbore primind ca parametru

// o referinta la legatura parintelui

void StergereNod(NodArbore* &legaturaParinte)

{

// stergem nodul si subarborele corespunzator

StergereSubarbore(legaturaParinte);

// modificam legatura paeintelui

legaturaParinte = NULL;

}

// sterge recursiv un subarbore

void StergereSubarbore(NodArbore *nod)

{

// conditia de oprire din recursie

if (nod == NULL)

return;

// stergem subarborii

for (int i = 0; i < nod->numarLegaturi; i++)

StergereSubarbore(nod->Legaturi[i]);

// stergem nodul curent

delete [] nod->Legaturi; // stergem vectorul de legaturi

delete [] nod; // stergrm nodul

}