Introducere in Stiinta Calculatoarelor 2013 | Page 62

Operaţii cu arbori
Fiind liste, arborii prezintă categorii de operaţii similare listelor, prin
care se afectează structura de noduri şi legături sau se accesează valorile
elementelor. Deci prelucrarea elementelor în arbore necesită două
acţiuni de avans în arbore – avans stânga şi avans dreapta, precum şi o
acţiune de acces şi prelucrare a valorii nodului curent – numita operație
de vizitare. Operaţii posibile sunt:
 Parcurgerea arborelui constă în vizitarea succesivă a nodurilor
acestuia. Privind modul de succesiune al vizitării nodurilor, există
trei modalităţi uzuale de parcurgere - după modul în care se pot
combina acţiunile de avans şi vizitare:
 Preordine: 1 – vizitare, 2 – avans stânga, 3 – avans dreapta;
 Inordine: 1 – avans stânga, 2 – vizitare, 3 – avans dreapta;
 Postordine: 1 – avans stânga, 2 – avans dreapta, 3 – vizitare.
Aceste modalităţi de parcurgere se pot aplica şi recursiv .
 Inserarea şi ştergerea unui nod din arbore – similar celor de la liste
liniare.
 Determinarea înălţimii arborelui.
 Determinarea succesorului sau predecesorului unui nod în arbore.
 Extragerea unui sub-arbore.
Operaţiile de parcurgere ale arborelui din figura 16 sunt ilustrate în
figura 17– prin succesiunea de noduri obţinute în fiecare caz.

Figura 17. Parcurgerea arborelui binar

După cum s-a arătat anterior, structurarea arborescentă este foarte
eficientă în prelucrarea datelor, cum sunt căutarea în volume mari de
date, calculul expresiilor respectând precedenţa operatorilor,
clasificarea obiectelor.
62