Arbori

2020/03/20 in Programare in C

Arborii, ca si listele, sunt structuri de date de natura recursiva si dinamica. In multe lucrari de specialitate, arborele se defineste recursiv.

Prin arbore se intelege o multime finita si nevida de elemente numite noduri:

A = {A1, A2, ..., An}, pentru n > 0

care au urmatoarele proprietati:

• exista un nod si numai unul care se numeste radacina arborelui;
• celelalte noduri formeaza submultimi disjuncte ale lui A, care formeaza fiecare cate un arbore.
  Arborii respectivi se numesc sub-arbori ai radacinii.

Un arbore poate fi reprezentat intr-un plan. Nodurile se reprezinta prin cercuri. Asa de exemplu, daca A1 este este radacina arborelui A, atunci figuram in plan un cerc pe care il marcam cu A1.

Fie acum:

{Ai1, Ai2, ..., Aik}

un subarbore al lui A1. Deoarece acesta este el insusi un arbore, fie Ai1 radacina lui. Lui Ai1 ii corespunde un cerc pe care il marcam cu Ai1. Acest cerc se figureaza sub cercul corespunzator lui A1. Cele doua cercuri se unesc ca in figura de mai jos:

In mod analog, daca:

{Aj1, Aj2, ..., Ajr}

este un subarbore al radacinii A1 si Aj1 este radacina acestui subarbore, atunci lui Aj1 ii corespunde un cerc care se traseaza sub cercul corespunzator lui A1. De asemenea, cercul marcat cu A1 se uneste si cu cel marcat cu Aj1. De obicei, cercurile marcate cu Ai1 si Aj1 se afla pe aceeasi orizontala, ca in figura de mai jos:

Acest proces continua cu toti subarborii radacinii A1. Apoi se continua cu subarborii lui Ai1, Aj1 s.a.m.d.

Intr-un arbore exista noduri carora nu le mai corespund subarbori.
Un astfel de nod se numeste terminal sau frunza.

In legatura cu arborii s-a incetatenit un limbaj conform caruia un nod radacina se spune ca este un nod tata (eng. parent), iar subarborii radacinii sunt descendentii acestuia. Radacinile descendentilor unui nod tata sunt fiii lui (eng. child). Astfel, in exemplul de mai sus, A1 este un nod tata, iar Ai1 si Aj1 sunt fii ai acestuia.

Deci, daca A este este un nod radacina si daca acesta are p subarbori a caror radacini sunt B1, B2, ..., Bp, atunci A este un nod tata, iar B1, B2, ..., Bp sunt fiii lui.

Despre nodurile B1, B2, ..., Bp se spune ca sunt frati.

Numarul fiilor unui nod tata este ordinul nodului tata respectiv.

In exemplul de mai sus, nodul A are ordinul p. Un nod frunza nu are fii, deci ordinul lui este 0.

O alta notiune legata de arbori este notiunea de nivel. Radacina unui arbore are nivelul 1.
Daca un nod are nivelul n, atunci fiii lui au nivelul n + 1.

Daca pentru fiecare nod, subarborii lui sunt ordonati (se considera intr-o anumita ordine), atunci arborele se considera ordonat. In acest caz, se obisnuieste sa se spuna ca radacina primului subarbore este fiul cel mai in varsta, iar radacina ultimului subarbore este fiul cel mai tanar.

In multe aplicatii practice intalnim asa-numitii arbori binari.
Un arbore binar este o multime finita de elemente care sau este vida sau contine un element numit radacina, iar celelalte elemente se impart in doua submultimi disjuncte, care fiecare la la randul ei este un arbore binar. Una dintre submultimi este numita arborele stang al radacinii, iar cealalta subarborele drept. Arborele binar este ordonat, deoarece in fiecare nod, subarborele stang se considera ca precede subarborele drept. De aici rezulta ca un nod al unui arbore binar are cel mult doi fii si ca unul este fiul stang, iar celalalt este fiul drept. Fiul stang este mai in varsta decat cel drept. Un nod al unui arbore binar poate sa aiba numai un descendent. Acesta poate fi arborele stang sau arborele drept.

Cele doua posibilitati se considera distincte. Cu alte cuvinte, daca doi arbori binari difera numai prin aceea ca nodul A dintr-un arbore are ca descendent numai fiul stang, iar acelasi nod din celalalt arbore are ca descendent numai fiul drept, cei doi arbori se considera distincti.

Un arbore binar nu se defineste ca un caz particular de arbore ordonat. Astfel, un arbore nu este niciodata vid, spre deosebire de un arbore binar care poate fi si vid.

Un arbore ordonat poate fi totdeauna reprezentat printr-un arbore binar (vezi fig. 3).

Transformarea se obtine destul de simplu si anume:

Se leaga impreuna fratii descendenti ai unui acelasi nod tata si se suprima legaturile lor cu nodul tata, exceptand legatura primului dintre ei.

De exemplu, arborele din figura de mai jos:

se transforma in arborele binar:

In arborele transformat:

• A are pe B ca fiu stang;
• B are pe C ca fiu drept si pe E ca fiu stang;
• C are pe D ca fiu drept.

PPrin regula de mai sus, rezulta ca primul fiu al unui nod tata devine fiul stang (cel mai varstnic). Celelalte legaturi formeaza subarbori dreprti: al doilea fiu devine fiul drept al primului, al treilea fiu devine fiul fiul drept al celui de-al doilea s.a.m.d.

In continuare ne vom ocupa numai de arborii binari.

Un nod al unui arbore binar este o data structurata de tipul TNOD care se defineste in felul urmator:

typedef struct tnod {
   declaratii
   struct tnod *st;
   struct tnod *dr;
} TNOD;

unde:

Asupra arborilor binari se pot defini mai multe operatii, dintre care:

• inserarea unui nod frunza intr-un arbore binar;
• accesul la un nod al unui arbore;
• parcurgerea unui arbore;
• stergerea unui arbore.

Operatiile de inserare si accesul la un nod au la baza un criteriu care a defineasca locul in arbore al nodului in cauza. Acest criteriu este dependent de problema concreta la care se aplica arborii binari pentru a fi rezolvata. El se defineste printr-o functie pe care o vom numi in continuare functia criteriu. Ea are doi parametri care sunt pointeri spre tipul TNOD. Fie p1 primul parametru al functiei criteriu si p2 cel de-al doilea al ei. Atunci, functia criteriu returneaza:

Exemplu:

Sa consideram ca la intrare se afla sirul de intregi: 20, 30, 5, 20, 4, 30, 7, 40

Se pune problema determinarii numarului de aparitii a fiecaruia.

Problema se poate rezolva daca se construieste un arbore binarale carui noduri au tipul TNOD definit astfel:

typedef struct tnod {
   int nr;
   int f;
   struct tnod *st;
   struct tnod *dr;
} TNOD;

Variabila nr are ca valoare unul din numerele citite la intrare, iar f reprezinta frecventa lui de aparitie in sirul de la intrare.

Intr-un nod frunza st = dr = 0 (pointerul nul).

La inceput se citeste valoarea 20 si arborele va contine un singur nod, corespunzator valorii 20:

nr = 20;
f = 1;
st = dr = 0;

Figuram arborele de la aceasta faza astfel:

La pasul urmator se citeste intregul 30 si se construieste data de tip TNOD corespunzatoare:

nr = 30;
f = 1;
st = dr = 0;

Aceasta data va fi inserata ca fiu drept al radacinii arborelui existent din pasul precedent.
Se obtine arborele:

Apoi se citeste valoarea 5 si nodul corespunzator acesteia se insereaza ca fiu stang al nodului corespunzator valorii 20.
Se obtine arborele:

Nodurile se insereaza in arbore in asa fel incat daca un nod corespunde intregului n, atunci subarborele stang al lui contine noduri care corespund la valori mai mici decat n, iar subarborele drept al sau contine noduri care corespund la valori mai mari decat n.

Se observa ca arborele de mai sus respecta aceasta regula.

In continuare se citeste valoarea 20 si cum exista deja in arbore un nod corespunzator acestei valori, se incrementeaza valoarea lui f din nodul respectiv.
In felul acesta se obtine reprezentarea:

La pasul urmator se citeste valoarea 4 si se construieste nodul corespunzator. Deoarece 4 < 20, nodul curent trebuie inserat in subarborele stang. Acesta este format din nodul corespunzator valorii 5.

Cum 4 < 5, rezulta ca nodul corespunzator lui 4 trebuie inserat in in subarborele corespunzator lui 5. Cum nu exista un astfel de subarbore, rezulta ca nodul corespunzator lui 4 devine fiu stang al nodului corespunzator lui 5.
Se obtine reprezentarea:

In continuare se citeste valoarea 30 si se construieste nodul corespunzator ei.

Cum 30 > 20, nodul se va insera in subarborele drept al lui 20. Acest subarbore este format dintr-un singur nod, care corespunde lui 30 si rezulta ca el nu se mai insereaza in arbore, ci se incrementeaza f-ul corespunzator.
Se obtine reprezentarea:

Urmatorul numar citit este 7. Se construieste nodul corespunzator acestei valori. Deoarece 7 < 20, nodul se insereaza in subarborele stang corespunzator lui 20. Radacina acestui subarbore este nodul corespunzator lui 5. Cum 5 < 7, rezulta ca nodul curent se va insera in subarborele drept al lui 5. Intrucat nu exista un astfel de subarbore, nodul curent se va insera ca fiu drept al lui 5.
Se obtine arborele:

Ultima valoare citita este 40. Actionand ca mai sus, nodul 40 se va insera ca fiu drept al lui 30.
Arborele final va fi:

Se observa ca arborele construit respecta regula enuntata mai sus.

La construirea arborelui din acest exemplu s-a utilizat urmatorul criteriu pentru determinarea pozitiei de inserare a nodului curent corespunzator valorii citite:

1. p1 este pointer spre un nod al arborelui in care se face inserarea (initial, p1 pointeaza spre radacina arborelui);
2. p2 este pointer spre nodul curent (nodul de inserat);
3. daca p2 -> nr < p1 -> nr, atunci se va incerca inserarea nodului curent in subarborele stang al nodului spre care pointeaza p1;
4. daca p2 -> nr > p1 -> nr, atunci se va incerca inserarea nodului curent in subarborele drept al nodului spre care pointeaza p1;
5. daca p2 -> nr = p1 -> nr, atunci nodul curent nu se mai insereaza in arbore deoarece exista deja un nod corespunzator valorii citite si se va incrementa p -> f.

Acest criteriu se realizeaza imediat printr-o functie care are ca parametri pointerii p1 si p2 care returneaza valorile:

Functia se defineste ca mai jos:

int criteriu (TNOD *p1, TNOD *p2) {
   if (p2 -> nr < p1 -> nr)
      return -1;
   if (p2 -> nr > p1 -> nr)
      return 1;
   return 0;
}

In cazul descris la Punctul 5, nodul curent nu se mai insereaza in arbore, situatie care, in general, corespunde cazului cand functia criteriu returneaza valoarea 0. In acest caz, nodurile spre care pointeaza p1 si p2 se considera echivalente.

De obicei, la intalnirea unei perechi de noduri echivalente, nodul din arbore (spre care pointeaza p1) este supus unei prelucrari, iar nodul curent (spre care pointeaza p2) este eliminat. Pentru a realiza o astfel de prelucrare este necesar sa se apeleze o functie care are ca parametri pointerii p1 si p2 si care returneaza un pointer spre tipul TNOD (de obicei se returneaza valoarea lui p1).

Vom numi aceasta functie echivalenta. Ea este dependenta de problema concreta, ca si functia criteriu.

Pentru exemplul de mai sus, functia echivalenta se defineste astfel:

TNOD *echivalenta (TNOD *p1, TNOD *p2) {
   p1 -> f++;
   elibnod(p2);
   return(p1);
}

Functia elibnod este o alta functie dependenta de problema concreta si care elibereaza zonele de memorie ocupate de nodul spre care pointeaza parametrul ei. Aceasta functie a fost intalnita in capitolul precedent si s-a utilizat in acelasi scop pentru nodurile din compunerea listelor.

O alta functie depemndenta de problema concreta este incnod, utilizata si ea in capitolul precedent.

Ea se apeleaza pentru a incarca datele in in nodul curent care urmeaza a fi inserat in arbore sau pentru a fi prelucrat de functia echivalenta, daca nu are loc inserarea.

In continuare se definesc functii pentru operatiile asupra arborilor amintite mai sus. Toate functiile utilizeaza o variabila globala care este un pointer spre radacina arborelui. Numim prad aceasta variabila. Ea se defineste astfel:

TNOD *prad;

In cazul in care intr-un program se prelucreaza simultan mai multi arbori, nu se va utiliza variabila globala prad, interfata dintre functii realizandu-se cu ajutorul unui parametru care este pointer spre tipul TNOD si caruia i se atribuie, la apel, adresa nodului radacina al arborelui prelucrat prin functia apelata.

In continuare se vor defini functii care utilizeaza variabila globala prad.

Functiile incnod, criteriu, echivalenta si elibnod pot avea si alte denumiri si pot fi utilizate prin intermediul parametrilor.

12.1. Inserarea unui nod frunza intr-un arbore binar