Unelte utilizator

Unelte site


laboratoare:laborator-04

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Ambele părți revizuirea anterioară Versiuni anterioare
Urmatoarea versiune
Versiuni anterioare
Ultima versiune Ambele părți următoarea reviziune
laboratoare:laborator-04 [2017/02/20 01:26]
florina_elena.barbu [4.1 Abstract Syntax Tree (Construcție Parse Tree)]
laboratoare:laborator-04 [2017/03/23 23:02]
iulian.matesica [5.1. Exerciții - schelet de laborator]
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ă**, **eliminând** condiţia de a exista **o singură legătură** ce pleacă dintr-un nod, adică maxim un singur nod "următor".
 +
 +===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), veri(cousins) etc.
 +
 +<note tip>Rădăcina NU poate fi nod-copil.</note>
 +
 +===Gradul(Degree)===
 +Gradul unui nod este egal cu numărul de copii ai acestuia.
 +
 +===Frunză(Leaf) şi nod intern/extern(internal/external)===
 +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 "coborî"(mergând numai de la părinte la copil) de la S la U.
 +
 +===Strămoş(Ancestor)===
 +Nodul S este strămoşul nodului U dacă U este urmaşul lui S(putem "urca" de la U la S).
 +<note tip>Rădăcina este strămoşul tuturor celorlalte noduri din arbore.</note>
 +
 +===Înălţime(Height)===
 +Definim înălţimea unui nod egală cu numărul de legături pe care "coborâm" de la acel nod la cea mai îndepărtată frunză.
 +<note tip>înălţimea arborelui = înălţimea rădăcinii</note>
 +
 +===Adâncime(Depth)===
 +Definim adâncimea unui nod egală cu cu numărul de legături pe care "coborâm" de la rădăcină la nodul respectiv.
 +<note tip>adâncimea rădăcinii = 0</note>
 +
 +===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/vector)===
 +
 +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
 +</file>
 +
 =====2 Arbori binari===== =====2 Arbori binari=====
 ====2.1 Definiție==== ====2.1 Definiție====
Linia 15: Linia 72:
 Arborii sunt folosiți in general pentru a modela o ierarhie de elemente.Astfel,fiecare element **(nod)** poate deține un număr de unul sau mai mulți descentenți,iar în acest caz nodul este numit **părinte** al nodului descendent.\\ Arborii sunt folosiți in general pentru a modela o ierarhie de elemente.Astfel,fiecare element **(nod)** poate deține un număr de unul sau mai mulți descentenți,iar în acest caz nodul este numit **părinte** al nodului descendent.\\
 Un nod fără descendenți este un **nod terminal**, sau **nod frunză**.\\ Un nod fără descendenți este un **nod terminal**, sau **nod frunză**.\\
 +{{ :laboratoare:arborebinar.png?400 |
 +# 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>Puteţi întâlni **variante diferite** pentru ultimele trei definiţii şi, de aceea, pot apărea confuzii legate de semnificaţia termenilor **plin, complet şi perfect**. În cazul în care aveţi de lucrat cu arbori binari plini/compleţi/perfecţi, asiguraţi-vă că toată lumea se referă la aceleaşi noţiuni.</note>
  
-# poza arbore# 
  
 ====2.2 Reprezentare==== ====2.2 Reprezentare====
Linia 37: Linia 107:
 void search_tree_preordine (tree *root) { void search_tree_preordine (tree *root) {
      if( root!=NULL){      if( root!=NULL){
-          count << root->data <<"\n";+          cout << root->data <<"\n";
           search_tree_preordine(root->left);           search_tree_preordine(root->left);
           search_tree_preordine(root->right);           search_tree_preordine(root->right);
Linia 167: Linia 237:
  
  
-=====5 Exerciții==== +=====5.1. Exerciții - schelet de laborator==== 
-  - Să se realizeze stocul unei farmacii,știind că informațiile pentru medicamentele unei farmacii sunt:nume medicament,preț,cantitate,data primirii,data expirării. +Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o.  
-    Evidența medicamentelor se ține cu un program care are drept structură de date un arbore de căutare după nume medicament.+ 
 +=== Linux=== 
 +Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare. 
 + 
 +  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab4_arbori-skel.zip%%'' 
 +  * ''%%unzip lab4_arbori-skel.zip%%'' 
 + 
 +Pentru compilare folositi comanda ''%%make%%''. Pentru rulare puteti folosi comanda ''%%make run%%'' sau ''%%./tree%%''
 +=====5.2. Exerciții==== 
 +  - 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. 
 +  - 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ă  întregi. Scrieţi o funcţie care verifică dacă o valoare dată se află în arbore(căutare). 
 +  - 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,știind că informațiile pentru medicamentele unei farmacii sunt:nume medicament,preț,cantitate,data primirii,data expirării. 
 + 
 +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 265:
 *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 "mică" decât o dată specificată de la terminal 
-*Determinați greutatea arborelui și verificați dacă este binar complet sau nu+*Determinați greutatea(fie greutatea = numărul de frunze) arborelui și verificați dacă este binar complet sau nu 
 + 
 +===Probleme de interviu=== 
 +  * Se dă V(un vector de n întregi) şi  P(un vector de taţi de lungime n). Verificaţi dacă se poate construi un arbore binar de căutare cu valorile din V şi legăturile copil-părinte din P. 
 +  * Fie un arbore binar perfect cu înălţimea H. Creaţi (H + 1) vectori/liste, câte unul/una pentru fiecare nivel din arbore. Afişaţi fiecare nivel(parcurgerea în lăţime) cu ajutorul vectorilor/listelor. 
 +  * Găsiţi cel mai apropiat strămoş comun pentru două noduri dintr-un arbore binar. 
 +  * Se dau doi arbori binari cu întregi, A1 şi A2, iar A1 conţine mult mai multe noduri decât A2. Verificaţi dacă A2 arată la fel ca un subarbore din A1.(“Arată la fel”, adică valorile întregi sunt aceleaşi)
  
laboratoare/laborator-04.txt · Ultima modificare: 2018/02/25 22:34 de către mihai.iacov