Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor

Laborator
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 5 în total
Cuvinte : 1435
Mărime: 100.63KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Vlariu Iorga

Extras din document

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);

Preview document

Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor - Pagina 1
Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor - Pagina 2
Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor - Pagina 3
Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor - Pagina 4
Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor - Pagina 5

Conținut arhivă zip

  • Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor.pdf

Alții au mai descărcat și

Probleme Algoritmi de Programare

1. Se da sirul de numere x1, x2, &,xn. Sa se determine numarul termenilor sirului dat apartinând unui interval [A,B] si sa se calculeze produsul...

Arbori

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n momentul de fata prelucrarea informatiilor de orice...

Arborii Partiali de Cost Minim

Arbori partiali de cost minim Fie G = <X, V> un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.Un arbore este...

Arbori Binari de Cautare

Arbori binari de cautare 1. Definiţii Un arbore este un graf orientat in care nu exista nici un ciclu(graf orientat aciclic) Un arbore binar...

Data types and addressing modes

1. Fundamental Data Types The fundamental data types of the Intel Architecture are - integer - ordinal - real - decimal - bytes - words -...

Baze de Date

– Cunoaşterea limbajului de manipulare a datelor utilizat la extragerea informaţiilor prin intermediul clauzelor (SELECT, FROM, WHERE, GROUP BY,...

Structuri de Date și Algoritmi

Lucrarea 1 Evaluarea si masurarea timpului de executie al unui algoritm 1.Definitia unui tip de date abstract - TDA Un TDA este un model...

Baze de Date Relaționale

Notiuni introductive, concepte fundamentale Prin sistem se întelege un ansamblu (grupare) de elemente interdependente legate între ele pentru...

Ai nevoie de altceva?