Arbori
A. Clase de arbori binari:



B. Parcurgerea arborilor binari:



Parcurgeri arbori.jpg
Program cpp: fisier de intrare:


Arbori binari alocati dinamic
Fiecare nod al arborelui este memorat intr-o structura cu campurile:
- informaţie utila = valoarea memorata de nod
- informaţie de legătura = adresele subarborilor stang si drept

struct nod{
int v; informatie utila
nod *st,*dr; adrese subarbori stang si drept
};

nod *rad;

Aplicatie rezolvata:
Scrieti un program C++ in care sa cititi nodurile unui arbore binar
si sa afisati sirurile parcurgerilor RSD, SRD şi SDR ale arborelui.



Arbori binari de cautare - ABC
Se numeşte arbore binar de căutare un arbore binar în care fiecare nod
are o cheie unică de identificare, care respectă proprietăţile:
- orice cheie asociată unui nod din subarborele stâng al unui nod
este mai mică decât cheia asociată nodului respectiv
- orice cheie asociată unui nod din subarborele drept al unui nod
este mai mare decât cheia asociată nodului respectiv

arbore_cautare.png

Asupra unui arbore de căutare pot fi efectuate mai multe operatii.
Cele mai importante sunt operatiile de :
a) Inserare b) Căutare c) Ştergere

a) Inserare = adaugarea unui nod într-un arbore de căutare,
cu păstrarea proprietăţii de arbore de căutare

Paşii pentru inserarea unui nod în arbore sunt:
Dacă arborele este nevid atunci avem cazurile:
i. valoarea coincide cu cheia vârfului - se renunţă la inserare,
deoarece cheile din arbore sunt unice;
ii. valoarea căutată este mai mică decât cheia asociată nodului,
căutarea continuă pentru subarborele stâng
iii. valoarea căutată este mai mare decât cheia asociată nodului,
căutarea continuă pentru subarborele drept

b) Căutarea unei valori în arbore.

Paşii pentru operaţia de căutare sunt:
Dacă arborele este nevid atunci avem cazurile:
i. valoarea coincide cu cheia vârfului - căutarea se opreşte cu succes,
am găsit valoarea în arbore;
ii. valoarea căutată este mai mică decât cheia asociată nodului,
căutarea continuă pentru subarborele stâng
iii. valoarea căutată este mai mare decât cheia asociată nodului,
căutarea continuă pentru subarborele drept

c) Ştergerea unui nod din arbore
Paşii pentru operaţia de căutare sunt:
Dacă arborele este nevid atunci avem cazurile:
i. valoarea coincide cu cheia vârfului - am găsit valoarea în arbore
1. dacă nodul este terminal (subarborii stâng şi drept sunt vizi),
acesta este şters, iar adresa reţinută de nodul părinte pentru el va fi nulă;
2. dacă numai subarborele drept este nevid, nodul este şters,
iar nodul părinte va reţine, în locul adresei lui, adresa subarborelui drept;
3. dacă numai subarborele stâng este nevid, nodul este şters,
iar nodul părinte va reţine, în locul adresei lui, adresa subarborelui stâng;
4. dacă ambii subarbori sunt nevizi:
- se identifică cel mai din dreapta nod al subarborelui stâng;
- cheia nodului astfel identificat va fi memorată de nodul analizat;
- nodul astfel identificat se şterge, iar ştergerea se efectuează ca în
cazul în care nodul subordonează numai subarborele stâng (3)
ii. valoarea căutată este mai mică decât cheia asociată nodului,
operaţia de ştergere continuă pentru subarborele stâng

iii. valoarea căutată este mai mare decât cheia asociată nodului,
operaţia de ştergere continuă pentru subarborele drept

altfel
nu există în arbore o cheie egală cu valoarea dată,
iar operaţia de ştergere nu se poate efectua

Aplicaţie rezolvată:
Se citesc n numere naturale nenule. Inseraţi valorile citite într-un
arbore binar de căutare.
Observaţie: Prin parcurgerea în inordine SRD a unui arbore de căutare
se obţine şirul cheilor în ordine crescătoare.



C Forma poloneza a unei expresii aritmetice:
arbore sintactic.jpg
cu albastru - operatorii cu galben - operanzii
ex_fpp.jpg


Proiect "Arbori binari" - prezentare PowerPoint (PPT/PPTX)

Model:
I. Teorie:
-definiţia arborelui binar
-clase de arbori binari
-reprezentarea arborilor binari în memorie

II. 3x Arbori binari:
-reprezentare grafică (desen în Paint)
-şirul parcurgerilor RSD, SRD, SDR
-şirul nodurilor pe niveluri
-nivelurile arborelui şi înălţimea acestuia

III. Programe cpp:
-Programul cu parcurgerile RSD,SRD,SDR
-alte programe
-date de intrare şi rezultate

IV. Vector organizaţi ca arbori binari
-Scrieţi definiţia şi exemple pentru:
a) Arbore min-heap
b) Arbore max-heap
c) Arbore de căutare

V. Arbori asociaţi unor expresii aritmetice
-expresia aritmetică în forma obişnuită
-arborele sintactic asociat expresiei
-forma poloneză prefixată (RSD)
-forma poloneză postfixată (SDR)