Arbori C++
Arborii sunt un caz particular al grafurilor. Acestia sunt compusi dintr-o serie de noduri interconectate in care se gasesc informatii.
Definitie: Arborele este un graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.
Radacina unui arbore este un nod special care ajuta la delimitarea arborelui pe nivele. Acest nod se afla pe cel mai inalt nivel din arbore.
Astfel, arborele devine mai usor de parcurs, deoarece plasarea nodurilor pe nivele duce la o structurare mai eficienta a informatiilor. De asemenea, algoritmii ce folosesc arbori sunt foarte usor de implementat recursiv, caci la fiecare pas, putem separa arborele in mai multi arbori mai mici.
Exemplu de arbore:
Arborele de mai sus are ca radacina nodul F.
In arborele de mai sus, putem privi nodul B ca radacina, a unui nou arbore, mai mic (sub-arbore).
In continuare vom prezenta cateva notiuni utile in intelegerea arborilor. Vom folosi ca exemplu arborele de mai sus cu radacina F.
Arborele poate fi impartit in nivele astfel :
- F(nodul radacina) – Nivelul 1
- B si G – Nivelul 2
- A, D si I – Nivelul 3
- C, E si H – Nivelul 4
Un nod A este descendent al unui alt nod B, daca este situat pe un nivel mai mare decât B şi există un lanţ care le uneşte şi nu trece prin rădăcină.Mai multe despre lanturi gasiti aici.
Exemplu: In arborele de mai sus E este descendentul lui B, si al lui A.
Un nod A este fiu/descendent direct al unui alt nod B, daca este situat pe nivelul imediat urmator nodului B si exista muchie intre A si B.
Exemplu: In arborele de mai sus B si G sunt fii lui F(nodul radacina), A e fiul lui B, H e fiul lui I etc.
Un nod A este ascendent al unui alt nod B, daca este situat pe un nivel mai mic decat B si exista lant care le uneste si nu trece prin radacina.
Exemplu : In arborele de mai sus G este ascendentul lui H,B este ascendentul lui C.
Un nod A este parinte al unui alt nod B, daca este situat pe nivelui imediat superior nodului B si exista muchie intre A si B.
Exemplu: In arborele de mai sus F este parintele lui B,D este parintele lui E, I este parintele lui H etc.
Doua noduri sunt frati daca au acelasi parinte.
Exemplu : B si G sunt frati, A si D sunt frati.
Un nod este frunza daca nu are niciun fiu, adica se afla pe ultimul nivel.
Exemplu : In arborele nostru frunzele sunt C,E si H.
Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂
Am mai intalnit in probleme notiunea de vectori de tati. Puteti oferi cateva informatii cu privire la acest lucru?(Si cu exemple, daca se poate)
Multumesc.
Salut. Un vector de tati este un vector in care putem sa retinem parintele fiecarui nod. El este util cand am dori sa facem o reconstruire de drum intr-un graf sau arbore (de exemplu dupa o parcurgere Breadth first search). Un exemplu de vector de tati : [0,1,1,2,3]. Aici nodul 1 este radacina, nodurile 2 si 3 sunt conectate cu nodul 1, nodul 4 cu nodul 2 si nodul 5 cu nodul 3.
Vedeti ca ati gresit teoria la ce inseamna un nod frunza. E un nod terminal, nu neaparat de pe ultimul nivel
Vedeti ca ati gresit teoria la ce inseamna un nod frunza. E un nod terminal, nu neaparat de pe ultimul nivel
fuarte frumos lectia arata cum e si in viata noastra adica arborele vietii ca toti avem rude viata este fuarte frumoasa si aici putem so reprezentam in c++ adica la informatica frumos imi place
numi place, adi buzi schimba ti fata
Adi bulz schimbați fața odată
Beldea Andrei schimbă fața lui Adi Bulz
Față schimbată cu succes!
beldea andrei aici.
schimbati fata ba adrian andrei
De ce nu mă asculți Adi Bulz, schimbați fața!!!!!!
adi bulz e frumy