1

CAPITOLUL AL IV-LEA. STRUCTURI ARBORESCENTE

1. Arbori şi operaţii cu arbori

Cele mai importante structuri neliniare care apar în algoritmi sunt structurile arborescente. Prin ele se pot descrie diferite ramificaţii. Un arbore este o mulţime finită A de unul sau mai multe noduri din care se distinge un nod R numit rădăcină toate celelalte noduri din A fiind partiţionate în n ≥ 0 mulţimi disjuncte A1, A2, ..., An, fiecare dintre aceste mulţimi fiind la rândul ei un arbore numit subarbore al rădăcinii R. Numărul de subarbori ai unui nod se numeşte gradul acelui nod. Nodurile cu gradul zero se numesc noduri terminale, frunze sau noduri externe. Celelalte noduri se numesc noduri de ramificare sau noduri interne. O mulţime de arbori se numeşte pădure. Pentru un arbore se defineşte nivelul unui nod în felul următor: rădăcina arborelui are nivelul 1 şi rădăcina unui subarbore al unui nod are nivelul cu 1 mai mare decât nivelul nodului respectiv. Se defineşte înălţimea unui arbore nivelul maxim al nodurilor din acel arbore. Dacă ordinea relativă a subarborilor fiecărui nod în parte este semnificativă spunem că arborele este un arbore ordonat. Pentru precizarea poziţiilor unor noduri ale arborilor în raport cu alte noduri se folosesc noţiuni utilizate în arborii genealogici. Rădăcinile subarborilor unui nod se numesc fii acestuia, nodul fiind tatăl acestor rădăcini. Doi fii ai unui nod sunt fraţi între ei. Rădăcina arborelui nu are tată. O clasă particulară de arbori o formează arborii binari. Se numeşte arbore binar un arbore în care fiecare nod are cel mult doi subarbori, unul stâng şi celălalt drept, şi, când are un singur subarbore, se face precizarea dacă este subarbore stâng sau subarbore drept. Dintre operaţiile posibile cu arbori un rol important îl deţine parcurgerea arborilor. Prin parcurgerea arborilor se înţelege considerarea unei ordini totale asupra nodurilor din arbore. Astfel se poate spune pentru orice nod care nod îl precede şi care îl succede logic. Orice permutare de noduri este o parcurgere, dar numai unele dintre ele sunt semnifictive pentru o structură arborescentă. Astfel, pentru arborii binari se folosesc de obicei trei tipuri de parcurgere: • parcurgerea în preordine, în care se prelucrează rădăcina, apoi se parcurge în preordine

subarborele stâng şi se parcurge în preordine subarborele drept; • parcurgerea în inordine, în care se parcurge în inordine subarborele stâng, apoi se

prelucrează rădăcina şi se parcurge în inordine subarborele drept; • parcurgerea în postordine, în care se parcurge în postordine subarborele stâng apoi se

parcurge în postordine subarborele drept şi se prelucrează rădăcina. Se consideră că parcurgerea unui arbore vid nu produce nici o acţiune, arborele respectiv

fiind considerat parcurs. Diferitele tipuri de parcurgeri definesc reguli de deplasare într-un

2

arbore, de examinare sistematică a nodurilor lui în aşa fel încât fiecare nod să fie considerat o singură dată.

Pentru arbori oarecare se folosesc următoarele parcurgeri: • parcurgerea în preordine, în care se prelucrează rădăcina, apoi se parcurg în preordine

subarborii acestei rădăcini; • parcurgerea în postordine, în care se parcurg în postordine subarborii corespunzători

rădăcinii apoi se prelucrează rădăcina. Pot fi efectuate şi alte tipuri de operaţii cu arbori cum ar fi adăugarea unor noi noduri,

eliminarea unor noduri, combinarea a doi sau mai mulţi arbori, copierea unui arbore şi altele asemenea.

2. Reprezentarea arborilor binari

Modul de reprezentare a arborilor binari este de obicei prin folosirea unor celule ce conţin câmpurile: INFO în care se pun datele asociate nodului respectiv, LS care conţine legătura la celula în care se află nodul fiu din stânga şi LD care conţine legătura la celula în care se află nodul fiu din dreapta al nodului respectiv.

În unele aplicaţii este util şi un al treilea câmp de legătură numit TATA care conţine legătura la celula în care se află tatăl nodului respectiv. Parcurgerea unui arbore binar cu această reprezentare se face cu ajutorul unei stive. Lăsăm cele trei tipuri de parcurgere ale arborilor binari sub forma de reprezentare anterioară ca exerciţii. Se poate face o parcurgere fără stivă dacă în locul legăturilor Λ se pune legătură la nodul ce precede în parcurgere nodul dat în cazul unei legături LS şi legătură la nodul care succede în parcurgere nodul dat în cazul unei legături LD. Aceste legături trebuie deosebite de legăturile obişnuite (către fii) printr-un marcaj. Se obţine astfel o structură arborescentă însăilată. Propunem ca exerciţii şi parcurgerile structurilor însăilate. Există şi alte tipuri de implementare a arborilor binari. Un astfel de model este folosit în sortarea de ansamble pe care o vom prezenta în capitolul 6.

3. Reprezentarea arborilor oarecare

Un arbore oarecare poate fi reprezentat ca o structură de liste. Un exemplu este dat în

figura următoare. Am pus marcajul - (1) dacă celula conţine numai legături şi + (0) dacă celula conţine şi date.

3

Pentru parcurgerea unui arbore reprezentat sub această formă este necesară o stivă în care se păstrează adresele celulelor din care urmează să se plece după partea de legătură sau chiar aceste legături (eliminând legăturile nule). Prezentăm în continuare un algoritm care parcurge structura corespunzătoare unui arbore şi dă cuvântul liniar cu paranteze corespunzător lui. Se notează celulele prin Ei, adresa primei celule prin init, marcajul celulei prin M(Ei), partea de dată prin D(Ei) şi partea de legătură (adresă) prin A(Ei). Se foloseşte de asemenea o stivă S care memorează adresa celulelor care urmează să li se ia partea de legătură pentru a parcurge mai departe structura şi un indicator k pentru a indica dacă trebuie să se deschidă sau să se închidă paranteza. Algoritmul 4.1. (parcurgere arbore tip structură de liste) 1. se face S = ∅, k = 1 şi i = init 2. dacă i = 0 atunci se merge la pasul 7 3. dacă M(Ei) = + atunci se pune D(Ei) în cuvântul de ieşire, se face i = A(Ei) şi se merge la

pasul 6 4. dacă k = 0 atunci se face k = 1 şi se merge la pasul 6 5. se pune ( în cuvântul de ieşire 6. se face A(Ei)⇒ S, i = D(Ei) şi se merge la pasul 3 7. dacă k = 0 atunci se pune ) în cuvântul de ieşire 8. dacă S ≠ ∅ atunci se face i ⇐ S, k = 0 şi se merge la pasul 2; altfel STOP

Se poate face parcurgerea arborelui fără o stivă suplimentară dacă în loc să punem zero în partea de legătură a ultimului element al unei liste ce corespunde unui nod diferit de rădăcină punem o legătură la celula din care s-a ajuns la această listă. Se obţine astfel o structură de liste numită structură filetată sau circulară. Vom numi legăturile adăugate adrese de întoarcere. În acest caz se folosesc două marcaje pentru fiecare celulă. Primul marcaj este cel anterior, 0 sau 1 după cum celula este de date sau de legătură, şi al doilea marcaj este 1 sau 0, după cum celula

4

corespunzătoare este ultima în listă sau nu. Ultima celulă a listei corespunzătoare rădăcinii conţine 0 în partea de legătură, aceasta indicând sfârşitul structurii. De exemplu, în figura următoare este reprezentată structura filetată ce corespunde la arborele din figura precedentă. Adresele de întoarcere au fost reprezentate punctat.

Se poate da un algoritm asemănător pentru a scrie cuvântul parantezat corespunzător unui arbore sub formă de structură filetată. Notaţiile sunt aceleaşi ca la algoritmul anterior, numai că M1(Ei) şi M2(Ei) sunt primul, respectiv al doilea marcaj, iar k indică dacă o celulă de legătură este atinsă pentru prima sau a doua oară. Algoritmul 4.2. (parcurgere arbore tip structură filetată) 1. se face k = 1 şi i = init 2. dacă i = 0 atunci STOP 3. dacă M1(Ei) = 0 atunci se merge la pasul 6 4. dacă k = 1 atunci se face k = 0, i = D(Ei) şi se merge la pasul 3 5. dacă M2(Ei) = 1 atunci se pune ) în cuvântul de ieşire; altfel se face k = 1 6. se face i = A(Ei) şi se merge la pasul 2 7. se pune în cuvântul de ieşire A(Ei); dacă M2(Ei) = 1 atunci se merge la pasul 6 8. se pune ( în cuvântul de ieşire, se face k = 1 şi se merge la pasul 6

Structurile de liste circulare nu pot fi folosite în cazul când o sublistă este distribuită de două sau mai multe liste. Dacă însă se folosesc mai multe elemente finale cu diferite adrese de întoarcere, atunci pentru parcurgere este necesară din nou folosirea unei stive. Structurile de liste prezentate pot fi parcurse fără stivă numai într-un singur sens. Pentru a parcurge aceste structuri în ambele sensuri, fiecare celulă a listei este prevăzută cu câte două legături, una către elementul care îl precede logic şi alta către cel care îl seccede. Aceste structuri de liste se numesc structuri simetrice.

5

Un alt mod de reprezentare a arborilor oarecare este folosirea unor celule ce conţin câmpurile: INFO în care se pun datele asociate nodului respectiv, FIU care conţine legătura la celula în care se află primul dintre fii nodului şi FRATE care conţine legătura la celula în care se află următorul frate al nodului. În unele aplicaţii este util şi un al treilea câmp de legătură numit TATA care conţine legătura la celula în care se află tatăl nodului respectiv. De exemplu, arborele din exemplul anterior se poate reprezenta sub forma alăturată. Pentru toate reprezentările de arbori este important de a cunoaşte rădăcina R a arborelui, deoarece prelucrările ce presupun structuri arborescente se fac, de obicei, plecând de la rădăcină şi urmând diferitele legături.

Sunt unele aplicaţii care se pot rezolva prin a stabili dacă două elemente aparţin sau nu la un acelaşi arbore. Astfel de structuri se pot reprezenta prin celule care conţin partea de informaţie şi câte o legătură către tatăl elementului. Rădăcina fiecărui arbore are legătura 0. Două elemente aparţin la acelaţi arbore dacă rădăcinile la care se ajung din ele coincid. Deci este suficient de a pleca din fiecare element şi urmând legăturile până se ajunge într-un nod care are legătura 0. Dacă aceste noduri coincid, atunci cele două noduri fac parte din acelaşi arbore, altfel ele fac parte din arbori diferiţi. Pentru reuniunea a doi arbori de această formă este suficient să definim drept tată al rădăcinii unuia dintre ei ca fiind rădăcina celuilalt arbore. Ca aplicaţii pot fi determinarea componentelor conexe şi tari conexe ale unui graf direcţionat, determinarea unui arbore parţial de cost minim pentru un graf nedirecţionat şi colorarea hărţilor pe care le propunem ca exerciţii.