| ... | Reprezentarea cu ajutorul grafurilor presupune: - existenta unui nod numit radacina - dispunerea nodurilor interne pe nivelui - existenta nodurilor terminale numite si noduri frunza |
| ... | Reprezentarea cu ajutorul modelului grafic presupune definirea elementului, ca zona de memorie formata din: - campul corespunzator informatiei utile - campurile definite ca variabile pointer cu ajutorul carora se refera descendentii. |
| Reprezentarea folosind functiile in() si out(0 arata ca un arbore are: - un nod radacina R pentru care in(R)=0 si out(R)>0 - noduri intermediare xi pentru care in(xi)=1 si out(xi)>0 - noduri frunza Fi pentru care in (Fi)=1 si out(Fi)=0. |
| ... | Reprezentarea cu ajutorul instructiunilor limbajului de programare, presupune definirea elementului sub forma unui sablon de forma: struct arbore_binar { struct informatie_utila info; struct arbore_binar * p_stang; struct arbore_binar * p_drept; }; Se pot defini tipuri echivalente pentru:,br> - zone de memorie cu typedef struct arbore_binar ARBIN; - pointer cu care sa se refere zone alocate dinamic prin typedef struct arbore_binar * PARBIN; |
| Pentru graful cu nodurile a1, a2, a3,..., an, se construieste o matrice boole4ana cu n linii si n coloane.
Matricea booleana contine 1 la intersectia liniei ai si coloanei a j daca cele doua noduri sunt legate cu un arc. In rest, matricea are elementele aij =0. |
| Fisierul de articole contine informatiile utile pentru descrierea reperelor si subansamblelor. |
| Fisierul de legaturi contine informatiile privind nodul parinte si nodul descendent . Vor fi atatea articole in acest fisier cate arce are arborele asociat unui produs finit rezultat intr-un proces de asamblare a reperelor si subansamblelor. |
| daca trebuie regasite rapid informatiile, fisierul de legaturi va contine in structura articolelor: - numele nodului parinte - adresa nodului parinte - numele nodului descendent - adresa nodului descendent. Aceste informatii se obtin cu usurinta prin faptul ca fisierul de repere (aqrticole) este un fisier cu inregistrari de lungime fixa. Se scriu programe care traverseaza acest fisier, memoreaza adresele articolelor si codurile reperelor si subanmsamblelor, informatii pe care le utilizeaza mai apoi la completarea fisierului de legaturi. Operatia se executa o singura data. |
| Arborele binar se reprezinta folosind: - un pointer cu care se refera radacina a - zone de memorie avand cate 3 campuri pentru informatia utila, pentru a referi cei doi descendenti. Pointerii de la nodurile frunza sunt initializati cu NULL. |
| Arborele binar se reprezinta folosind la definirea elementului, numarul maxim de pointeri ce corespund nodului cu cei mai multi descendenti. Areborele oarecare are bodul C cu 4 descendenti. Inseamna ca elemenul pentru descrierea nodurilor va avea 5 camuri, unul pentru informatia utila si 4 pentru pointeri. Se observa ca multe dintre campurile pointerilor sunt initializate cu NULL. |
| Arborele binar se reprezinta folosind un vector de pointeri alocat dinamic. Elementul va referi acest vector de pointeri. Elementul va contine 3 campuri: - informatie utila - numarul de descendenti - pointer spre vectorul de pointeri pentru memorarea informatiilor despre descendenti. |
| Arborele binar complet are toate frunzele pe ultimul nivel, iar pe celelalte niveluri nu are pointeri initializati cu NULL. |
| daca se porneste de la proprietatile arborelui binar complet, atunci pe nivelul 1 se afla 21-1 noduri, la nivelul 2 se afla 22-1 noduri, la nivelul h se afla 2h-1 noduri, iar la nivelul ultim, k, se afla 2k-1 noduri. Prin insumarea termenilor progreiei geometrice: S= 21-1 + 22-1 + 23-1 + ... + 2k-1 = 2k noduri, cate are in total un arbore complet binar cu k niveluri. |