Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-04 [2017/02/20 01:53] florina_elena.barbu [2.1 Definiție] |
laboratoare:laborator-04 [2017/03/12 22:05] mihai.iacov [5 Exerciții] |
||
---|---|---|---|
Linia 9: | Linia 9: | ||
\\ | \\ | ||
+ | ===== Noţiuni introductive===== | ||
+ | |||
+ | ===Definiţie generală=== | ||
+ | |||
+ | Un arbore poate fi definit ca: structură de date ce conţine noduri şi legături, fără circularitate. Un arbore poate fi văzut ca o extindere de la **lista simplu înlănţuită şi necirculară**, | ||
+ | |||
+ | ===Rădăcină(Root)=== | ||
+ | Numim rădăcină primul nod al arborelui(echivalentul capului de listă). | ||
+ | |||
+ | ===Copil - Părinte(Child - Parent)=== | ||
+ | Nodul P este părintele nodului C dacă are legătură către C(similar, C este copilul lui P). | ||
+ | * Pot apărea şi alţi termeni pentru relaţia dintre noduri: fraţi(siblings), | ||
+ | |||
+ | <note tip> | ||
+ | |||
+ | ===Gradul(Degree)=== | ||
+ | Gradul unui nod este egal cu numărul de copii ai acestuia. | ||
+ | |||
+ | ===Frunză(Leaf) şi nod intern/ | ||
+ | Numim frunză un nod fără copii(**nod terminal**). | ||
+ | * Frunzele se mai numesc **noduri externe**. | ||
+ | * Nodurile care au copii se mai numesc **noduri interne**. | ||
+ | |||
+ | ===Urmaş(Descendant)=== | ||
+ | Nodul U este urmaşul nodului S dacă putem " | ||
+ | |||
+ | ===Strămoş(Ancestor)=== | ||
+ | Nodul S este strămoşul nodului U dacă U este urmaşul lui S(putem " | ||
+ | <note tip> | ||
+ | |||
+ | ===Înălţime(Height)=== | ||
+ | Definim înălţimea unui nod egală cu numărul de legături pe care " | ||
+ | <note tip> | ||
+ | |||
+ | ===Adâncime(Depth)=== | ||
+ | Definim adâncimea unui nod egală cu cu numărul de legături pe care " | ||
+ | <note tip> | ||
+ | |||
+ | ===Nivel(Level)=== | ||
+ | Definim nivelul unui nod egal cu 1 + adâncimea. | ||
+ | |||
+ | ===Pădure(Forest)=== | ||
+ | Numim pădure o mulţime de N(de obicei N >= 2) arbori disjuncţi(care nu au noduri comune). | ||
+ | |||
+ | ===Vector de taţi(Parent array/ | ||
+ | |||
+ | Vectorul de taţi reprezintă o soluţie ieftină(d.p.d.v. al memoriei) de reprezentare a unui arbore atunci când nodurile pot avea un număr diferit de legături. În acest caz, ne putem folosi de faptul că **fiecare nod-copil are un singur părinte**, indiferent de câţi copii are părintele respectiv. **Rădăcina** arborelui este singura **excepţie**. | ||
+ | |||
+ | <file cpp> | ||
+ | //fie n = nr. de noduri | ||
+ | //nodurile sunt numerotate de la 0 la n-1 | ||
+ | //fie doua noduri numerotate cu indicii A si B | ||
+ | Parent[A] = B; // Parintele nodului A este nodul B | ||
+ | //fie Root nodul radacina | ||
+ | Parent[Root] = -1; //nu exista nod numerotat cu -1 | ||
+ | </ | ||
+ | |||
=====2 Arbori binari===== | =====2 Arbori binari===== | ||
====2.1 Definiție==== | ====2.1 Definiție==== | ||
Linia 17: | Linia 74: | ||
{{ : | {{ : | ||
# poza arbore#}} | # poza arbore#}} | ||
+ | |||
+ | ====Alte noţiuni introductive==== | ||
+ | ===Arbore binar plin=== | ||
+ | Un arbore binar este plin dacă nu există niciun nod intern la care mai putem lega un nod-copil nou(Toate nodurile, în afară de frunze, au număr maxim de copii). | ||
+ | |||
+ | ===Arbore binar complet=== | ||
+ | Un arbore binar este complet dacă fiecare nivel(**cu posibila excepţie a ultimului**) este complet ocupat. | ||
+ | |||
+ | ===Arbore binar perfect=== | ||
+ | Un arbore binar este perfect dacă este complet ocupat pe fiecare nivel(fără excepţii). | ||
+ | |||
+ | <note important> | ||
+ | |||
====2.2 Reprezentare==== | ====2.2 Reprezentare==== | ||
Linia 168: | Linia 238: | ||
=====5 Exerciții==== | =====5 Exerciții==== | ||
- | - Să se realizeze stocul unei farmacii, | + | - Se dă un vector cu n întregi. Scrieţi o funcţie care să creeze un arbore binar de căutare cu valorile din vector. |
- | Evidența medicamentelor se ține cu un program care are drept structură de date un arbore de căutare după nume medicament. | + | - Se dă un arbore binar ce stochează întregi. Scrieţi o funcţie care verifică dacă arborele este binar de căutare. |
+ | - Se dă un arbore binar de căutare ce stochează | ||
+ | - Acelaşi arbore – inserare(şi să rămână arbore de căutare) | ||
+ | - Acelaşi arbore – ştergere(şi să rămână arbore de căutare) | ||
+ | |||
+ | Puteţi testa primele 5 exerciţii în acelaşi program. | ||
+ | |||
+ | ===Problemă întreagă=== | ||
+ | * Să se realizeze stocul unei farmacii, | ||
+ | |||
+ | Evidența medicamentelor se ține cu un program care are drept structură de date un arbore de căutare după nume medicament. | ||
Să se scrie programul care execută următoarele operații: | Să se scrie programul care execută următoarele operații: | ||
*Creează arborele de căutare | *Creează arborele de căutare | ||
Linia 175: | Linia 255: | ||
*Tipăreste medicamentele în ordine lexicografică | *Tipăreste medicamentele în ordine lexicografică | ||
*Elimină un nod identificat prin nume medicament | *Elimină un nod identificat prin nume medicament | ||
- | *Creează un arbore de căutare cu medicamentele care au data de expirare mai meche decât o dată specificată de la terminal | + | *Creează un arbore de căutare cu medicamentele care au data de expirare mai " |
- | *Determinați greutatea arborelui și verificați dacă este binar complet sau nu | + | *Determinați greutatea(fie greutatea = numărul de frunze) |