Aplicații cu arbori binari - evaluarea arborilor asociați expresiilor

Obiective

In urma parcurgerii acestui laborator, studentul va fi capabil:

- sa inteleaga notiunea de arbore si structura unui arbore binar;

- sa construiasca, in limbajul C, un arbore binar, si sa realizeze o parcurgere a structurii de

date prin mai multe moduri;

- sa citeasca o expresie matematica si sa-i construiasca arborele binar asociat;

- sa evalueze o expresie matematica data printr-un arbore binar.

Notiuni teoretice

1. Notiunea de arbore. Arbori binari

Un arbore reprezinta o structura de date ce modeleaza o ierarhie de elemente. Astfel, fiecare

element, numit nod, poate detine un numar de unul sau mai multi descendenti, iar in acest caz

nodul este numit parinte al nodurilor descendente. Fiecare nod poate avea un singur nod parinte. Un

nod fara descendenti este un nod terminal, sau frunza. In schimb, exista un singur nod fara parinte,

iar acesta este intotdeauna radacina arborelui.

Un arbore binar este un caz special de arbore, in care fiecare nod poate avea maxim doi

descendenti, denumiti formal nodul stang, respectiv nodul drept. (Astfel, un nod cu un singur

descendent il poate considera pe acesta fie stang, fie drept.) In functie de elementele ce pot fi

reprezentate in noduri si de restrictiile aplicate arborelui, se pot crea structuri de date cu proprietati

deosebite: heap-uri, arbori AVL, arbori rosu-negru, arbori Splay si multe altele. O parte din aceste

structuri vor fi studiate la curs si in laboratoarele viitoare.

In acest laborator ne vom concentra asupra unei utilizari comune a arborilor binari, si anume pentru

a reprezenta si evalua expresii matematice de orice nivel de complexitate.

2. Reprezentarea arborilor binari

Exista mai multe moduri de reprezentare a arborilor, dintre care amintim reprezentarea prin vectori

(prezentata in detaliu la curs), care ofera gradul cel mai mare de generalitate.

In cazul arborilor binari, totusi, este posibila o reprezentare mai simpla, prin pointeri, definind o

structura pentru fiecare nod in felul urmator:

1/5

typedef struct tagNode {

void *key;

struct tagNode *left;

struct tagNode *right;

} Node;

unde key reprezinta cheia (valoarea) din nodul respectiv, iar left si right sunt pointeri catre

nodurile stang, respectiv drept, sau NULL in cazul in care ramura respectiva este inexistenta. Astfel,

un nod frunza are ambii pointeri setati NULL.

In acest sens, pornind de la un nod radacina root, de tipul Node, se pot accesa nodurile intregului

arbore. Deci arborele este complet determinat de un pointer la nodul radacina, si in toate functiile de

manipulare de arbori binari, pasarea acestui pointer este suficienta.

3. Parcurgerea arborilor

Parcurgerea arborilor se refera la ordinea in care sunt procesate nodurile dintr-un anumit arbore.

Exista mai multe moduri de parcurgere, dintre care amintim:

- parcurgerea in preordine (se parcurge Radacina, apoi subarborele Stang, apoi cel Drept -

RSD)

- parcurgerea in inordine (se parcurge subarborele Stang, apoi Radacina, apoi subarborele

Drept - SRD)

- parcurgerea in postordine (se parcurge subarborele Stang, apoi cel Drept, apoi Radacina -

SDR)

- parcurgerea in latime (se insereaza la inceput radacina intr-o coada, apoi la fiecare pas se

extrage un nod din coada, si se adauga in coada nodurile Stang, respectiv Drept, pana cand

coada devine goala)

De exemplu, pseudocodul functiei recursive pentru parcurgerea in inordine este ilustrat mai jos:

ParcurgereSRD(Node nod) {

if (nod->left)

ParcurgereSRD(nod->left);

Proceseaza(nod->key);