Diferențe

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

Link către această vizualizare comparativă

--- laboratoare:laborator-04 [2017/03/08 13:07]
mihai.iacov [2 Arbori binari]
+++ laboratoare:laborator-04 [2017/03/12 21:58]
mihai.iacov [5 Exerciții]
@@ Linia 16: / Linia 16: @@
 ===Rădăcină(Root)===
+Numim rădăcină primul nod al arborelui(echivalentul capului de listă).
-===Frunză(Leaf)===
 ===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.
-===Nivel(Level)===
+<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)===
@@ Linia 50: / Linia 74: @@
 {{ :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>
 ====2.2 Reprezentare====
@@ Linia 201: / Linia 238: @@
 =====5 Exerciții====
-  - Să se realizeze stocul unei farmacii,știind că informațiile pentru medicamentele unei farmacii sunt:nume medicament,preț,cantitate,data primirii,data expirării.
+  - 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ă  î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)
+===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:
 *Creează arborele de căutare

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină