sdacap08-1
DESCRIPTION
SDACap08-3TRANSCRIPT
-
8. Arbori
8.1. Arbori generalizai
8.1.1. Definiii
n definirea noiunii de arbore se pornete de la noiunea de vector.
Fie V o mulime avnd elementele a1, a2,....an.
Pe mulimea V se poate defini o aa numit "relaie de preceden" n felul urmtor: se spune c ai precede pe aj dac i < j. Aceasta se noteaz: aip aj.
Se poate verifica uor c relaia astfel definit are urmtoarele proprieti, valabile pentru structura de vector:
------------------------------------------------------------- (1) Oricare ar fi aV avem a a. (S-a notat cu relaia "nu precede"); p p (2) Dac ap b i bp c atunci a c (tranzitivitate); [8.1.1.a] p (3) Oricare ar fi aV i bV, dac a b atunci avem fie a b fie b a. p p-------------------------------------------------------------
Din proprietile (1) i (2) rezult c relaia de preceden nu determin n V bucle nchise, adic nu exist nici o secven de elemente care se preced dou cte dou i n care ultimul element este acelai cu primul, cum ar fi de exemplu a b c d a. p p p p
Proprietatea (3) precizeaz c relaia de preceden este definit pentru oricare dou elemente a i b ale lui V, cu singura condiie ca a b.
Fie V o mulime finit peste elementele creia s-a definit o relaie de preceden, stabilind referitor la fiecare pereche de elemente, care dintre ele l precede pe celallalt.
Dac aceast relaie posed proprietile [8.1.1.a], atunci ea imprima peste mulimea V o structur de vector (fig.8.1.1.a).
a b c d e
Fig. 8.1.1.a. Structur de vector
n figura 8.1.1.b apare o alt reprezentare intuitiv a unei structuri de vector. Sgeile din figur indic relaia "succesor".
a b c d e
Fig.8.1.1.b. Relaia succesor
-
Aceast relaie se definete cu ajutorul relaiei de preceden dup cum urmeaz: dac ntre elementele a i b ale lui V este valabil relaia a b i nu exist nici un cV astfel ca a c b atunci se zice c b este succesorul lui a.
pp p
Se observ c relaia "succesor" (mulimea sgeilor din figura 8.1.1.b.), precizeaz relaia "preceden" fr a fi ns identic cu ea. Spre exemplu, exist relaia b e (prin tranzitivitate), dar nici o sgeat nu conecteaz pe b cu e.
p
n figura8.1.1.c apare o aa numit structur de arbore care se definete prin generalizarea structurii de vector.
b c d
g hf e i j
n ol k m
a
p
nivelul 1
nivelul 2
nivelul 3
nivelul 4
nivelul 5
.
Fig. 8.1.1.c. Structur de arbore
Astfel, dac n cazul vectorului, toate elementele cu excepia ultimului au exact un succesor, la structura de arbore se admite ca fiecare element s aib un numr oarecare de succesori, inclusiv zero, cu restricia ca dou elemente distincte s nu aib acelai succesor. Relaia succesor definete o relaie de preceden pe structura de arbore. Astfel, din figura avem b p, d n, etc. p p
Relaia de preceden definit pe structura de arbore se bucur de proprietile (1) i (2) de la [8.1.1.a] dar nu satisface proprietatea (3).
ntr-adevr n figura 8.1.1.c, pentru elementele b i c nu este valabil nici una din relaiile b c sau c b, la fel pentru elementele d i k. Prin urmare, relaia de preceden este definit numai pentru o parte a perechilor de elemente ale arborelui, cu alte cuvinte este o relaie parial.
p p
n general, o structur de arbore se definete ca o mulime A de n 0 noduri de acelai tip, peste care s-a definit o relaie de preceden avnd proprietile (1) i (2) de la [8.1.1.a] precum i urmtoarele dou proprieti [8.1.1b]:
-------------------------------------------------------------
(3) Oricare ar fi b,cA, astfel nct bp c i c b, dac b d i c e atunci dp p p e. Cu alte cuvinte, dou elemente oarecare ntre care nu exist relaia de precede nu pot avea acelai succesor. [8.1.1.b]
-
(4) Dac A nu este vid (n >0) atunci exist un element numit rdcin, care precede toate celelalte elemente.
-------------------------------------------------------------
Pentru structura de arbore se poate formula i o alt definiie echivalent cu cea de mai sus.
Prin arbore, se nelege o mulime de n 0 noduri de acelai tip, care dac nu este vid, atunci are un anumit nod numit rdcin, iar restul nodurilor formeaz un numr finit de arbori, doi cte doi disjunci.
Se constat c att aceast definiie, ct i structura pe care o definete, sunt recursive, lucru deosebit de important deoarece permite prelucrarea simpl a unei astfel de structuri cu ajutorul unor algoritmi recursivi.
n continuare se vor defini cteva noiuni referitoare la arbori.
Prin subarborii unui arbore, se neleg arborii n care se descompune acesta prin ndeprtarea rdcinii.
Spre exemplu arborele din figura 8.1.1.c, dup ndeprtarea rdcinii a, se descompune n trei subarbori avnd rdcinile respectiv b,c i d.
Oricare nod al unui arbore este rdcina unui arbore parial.
Spre exemplu n aceeai figur, f este rdcina arborelui parial format din nodurile f, k, l, m i p.
Un arbore parial nu este ntotodeauna subarbore pentru arborele complet, dar orice subarbore este un arbore parial.
ntr-o structur de arbore, succesorul unui nod se mai numete i "fiul" sau "urmaul" su.
Dac un nod are unul sau mai muli fii, atunci el se numete "tatl" sau "printele" acestora.
Dac un nod are mai muli fii, acetia se numesc "frai" ntre ei.
Spre exemplu n fig. 8.1.1.c nodul b este tatl lui e, f i g care sunt frai ntre ei i sunt n acelai timp fiii lui b.
Se observ c ntr-o structur de arbore, arborele parial determinat de orice nod diferit de rdcin, este subarbore pentru arborele parial determinat de tatl su.
Astfel f este tatl lui m, iar arborele parial determinat de m este subarbore pentru arborele parial determinat de f.
ntr-o structur de arbore se definesc niveluri n felul urmtor: rdcina formeaz nivelul 1, fiii ei formeaz nivelul 2 i n general fiii tuturor nodurilor nivelului n formeaz nivelul n+1 (fig.8.1.1.c).
Nivelul maxim al nodurilor unui arbore se numete nlimea arborelui.
-
Numrul fiilor unui nod definete gradul nodului respectiv.
Un nod de grad zero se numete nod terminal (frunz), iar un nod de grad diferit de zero, nod intern.
Gradul maxim al nodurilor unui arbore se numete gradul arborelui.
Arborele din figura 8.1.1.c are nlimea 5, nodul d este de grad 2, nodul h este terminal, f este un nod intern iar gradul arborelui este 3.
Dac n1, n2,....,nk este o secven de noduri aparinnd unui arbore, astfel nct ni este printele lui ni+1 pentru 1 i< k, atunci aceast secven se numete "drum" sau "cale" de la nodul n1 la nodul nk.
Lungimea unui drum este un ntreg avnd valoarea egal cu numrul de ramuri (sgei) care trebuiesc traversate pentru a ajunge de la rdcin la nodul respectiv.
Rdcina are lungimea drumului egal cu 1, fiii ei au lungimea drumului egal cu 2 i n general un nod situat pe nivelul i are lungimea drumului i.
Spre exemplu, n figura 8.1.1.c, lungimea drumului la nodul d este 2 iar la nodul p este 5.
Dac exist un drum de la nodul a la nodul b, atunci nodul a se numete strmo sau ancestor al lui b, iar nodul b descendent sau urma al lui a.
Spre exemplu n aceeai figur, strmoii lui f sunt f, b i a iar descendenii si f, k, l, m i p.
Conform celor deja precizate tatl unui nod este strmoul su direct (predecesor) iar fiul unui nod este descendentul su direct (succesor).
Un strmos respectiv un descendent al unui nod, altul dect nodul nsui, se numete strmo propriu respectiv descendent propriu.
ntr-un arbore, rdcina este singurul nod fr nici un strmo propriu.
Un nod care nu are descendeni proprii se numete nod terminal (frunz).
nlimea unui nod ntr-un arbore este lungimea celui mai lung drum de la nodul respectiv la un nod terminal.
Pornind de la aceast definiie, nlimea unui arbore se poate defini i ca fiind egal cu nlimea nodului rdcin.
Adncimea unui nod este egal cu lungimea drumului unic de la rdcin la acel nod.
n practic se mai definete i lungimea drumului unui arbore numit i lungimea drumului intern, ca fiind egal cu suma lungimilor drumurilor corespunztoare tuturor nodurilor arborelui.
-
Formal, lungimea medie a drumului intern al unui arbore, notat cu PI se definete cu ajutorul formulei [8.1.1.c].
-----------------------------------------------------------
==
h
iiI inn
P1
*1 unde n = numrul total de noduri
i = nivelul nodului [8.1.1.c] ni =numrul de noduri pe nivelul i h = nalimea arborelui ----------------------------------------------------------- 8.1.2. Tipul de date abstract arbore generalizat
La fel ca i n cazul altor tipuri de structuri de date, este dificil de stabilit un set de operatori care s fie valabil pentru toate aplicaiile posibile ale structurilor de tip arbore.
Cu toate acestea, din mulimea operatorilor posibili se recomand pentru TDA Arbore generalizat forma prezentat n secvena [8.1.2.a].
------------------------------------------------------------- TDA Arbore generalizat Modelul matematic: arbore definit n sens matematic.
Elementele arborelui aparin unui aceluiai tip, numit i tip de baz.
Notaii: TipNod - tipul unui nod al arborelui; TipArbore - tipul arbore;
TipCheie - tipul cheii unui nod; N: TipNod;
A: TipArbore; v: TipCheie; [8.1.2.a] Operatori:
1. Tata(N: TipNod, A:TipArbore): TipNod; - operator care returneaz tatl (printele) nodului N din arborele A. Dac N este chiar rdcina lui A se returneaz "nodul vid";
2. PrimulFiu(N: TipNod, A: TipArbore): TipNod; - operator care returneaz cel mai din stnga fiu al nodului N din arborele A. Dac N este un nod terminal, operatorul returneaz "nodul vid".
3. FrateDreapta(N: TipNod, A:TipArbore): TipNod; operator care returneaz nodul care este fratele drept "imediat" al nodului N din arborele A. Acest nod se definete ca fiind nodul M care are acelai printe T ca i N i care n reprezentarea arborelui apare imediat n dreapta lui N n ordonarea de la stnga la dreapta a fiilor lui T.
4. Cheie(N: TipNod, A: TipArbore): TipCheie; - operator care returneaz cheia nodului N din arborele A.
-
5. Creazai(v: TipCheie, A1,A2,...,Ai: TipArbore): TipArbore; este unul din operatorii unei familii,
care are reprezentani pentru fiecare din valorile lui i=0,1,2,.. Funcia Creazai genereaz un nod nou R, care are cheia v i cruia i asociaz i fii. Acetia sunt respectiv subarborii A1, A2,...,Ai. n final se genereaz de fapt un arbore nou avnd rdcina R. Dac i=0, atunci R este n acelai timp rdcina i nod terminal.
6. Radacina(A: TipArbore): TipNod; - operator care returneaz nodul care este rdcina arborelui A sau nodul vid dac A este un arbore vid.
7. Initializeaza(A: TipArbore): TipArbore; - creaz arborele A vid.
8. Insereaza(N: TipNod, A: TipArbore, T: TipNod); - operator care realizeaz inseria nodului N ca fiu al nodului T n arborele A. n particular se poate preciza i poziia nodului n lista de fii ai tatlui T (prin convenie se accept sintagma cel mai din dreapta fiu).
9. Suprima(N: TipNod, A: TipArbore); - operator care realizeaz suprimarea nodului N i a descendenilor si din arborele A. Suprimarea se poate defini difereniat funcie de aplicaia n care este utilizat structura de date n cauz.
10. Inordine(A: TipArbore, ProcesareNod(...): TipProcedura); - procedur care parcurge nodurile arborelui A n inordine i aplic fiecrui nod procedura de prelucrare ProcesareNod.
11. Preordine(A: TipArbore, ProcesareNod(...): TipProcedura); - procedur care parcurge nodurile arborelui A n preordine i aplic fiecrui nod procedura de prelucrare ProcesareNod.
12. Postordine(A: TipArbore, ProcesareNod(...): TipProcedura); - procedur care parcurge nodurile arborelui A n postordine i aplic fiecrui nod procedura de prelucrare ProcesareNod.
-----------------------------------------------------------
Structura arbore generalizat este important deoarece apare frecvent n practic, spre exemplu arborii familiali, sau structura unei cri defalcat pe capitole, seciuni, paragrafe i subparagrafe.
Din punctul de vedere al reprezentrii lor n memorie, arborii generalizai au marele dezavantaj c au noduri de grade diferite, ceea ce conduce la structuri neuniforme de date sau la structuri uniforme parial utilizate.
-
8.1.3. Traversarea arborilor generalizai
Una din activitile fundamentale care se execut asupra unei structuri arbore este traversarea acesteia.
Ca i n cazul listelor liniare, prin traversarea unui arbore se nelege execuia unei anumite operaii asupra tuturor nodurilor arborelui.
n timpul traversrii, nodurile sunt vizitate ntr-o anumit ordine, astfel nct ele pot fi considerate ca i cum ar fi integrate ntr-o list liniar.
Descrierea i nelegerea celor mai muli algoritmi este mult uurat dac n cursul prelucrrii se poate preciza elementul urmtor al structurii arbore, respectiv se poate liniariza structura arbore.
n principiu tehnicile de traversare a arborilor generalizai se ncadreaz n dou mari categorii:
(1) Tehnici bazate pe cutarea n adncime (depth-first search)
(2) Tehnici bazate pe cutarea prin cuprindere (breadth-first search).
Aceste tehnici i au sorgintea n traversarea structurilor de date graf, dar prin particularizare sunt aplicabile i altor categorii de structuri de date, respectiv structurii de date arbore generalizat.
8.1.3.1. Traversarea arborilor generalizai prin tehnici bazate pe cutarea n adncime: preordine, inordine i postordine
Principiul cutrii n adncime (depth-first search) presupune:
(1) Parcurgerea n adncime a structurii, prin ndeprtare de punctul de pornire, pn cnd acest lucru nu mai este posibil.
(2) n acest moment se revine pe drumul parcurs pn la proximul punct care permite o nou posibilitate de naintare n adncime.
(3) Procesul continu n aceeai manier pn cnd structura de date este parcurs n ntregime.
Exist trei moduri de traversare (liniarizare) care se refer la o structur de date arbore generalizat, bazate pe cutarea n adncime i anume:
(1) Traversarea n preordine
(2) Traversarea n inordine
(3) Traversarea n postordine
-
Cele trei modaliti de traversare, se definesc de regul n manier recursiv, asemeni structurii de arbore i anume, ordonarea unui arbore se definete presupunnd c subarborii si s-au ordonat deja.
Cum subarborii au noduri strict mai puine dect arborele complet, rezult c, aplicnd recursiv de un numr suficient de ori definiia, se ajunge la ordonarea unui arbore vid, care este evident.
Cele trei moduri de traversare ale unui arbore generalizat A se definesc recursiv dup cum urmeaz:
o Dac arborele A este nul, atunci ordonarea lui A n preordine, inordine i
postordine se reduce la lista vid. o Dac A se reduce la un singur nod, atunci nodul nsui, reprezint
traversarea lui A, n oricare din cele trei moduri.
o Pentru restul cazurilor, fie arborele A cu rdcina R i cu subarborii A1, A2,..., Ak. (fig. 8.1.3.1.a):
. . .
R
A1 A2 Ak
Fig.8.1.3.1.a. Structur de arbore generalizat
1o. Traversarea n preordine a arborelui A presupune: Traversarea rdcinii R Traversarea n preordine a lui A1 Traversarea n preordine a lui A2, A3 i aa mai departe pn la Ak
inclusiv. 2o. Traversarea n inordine a arborelui A presupune:
Traversarea n inordine a subarborelui A1 Traversarea nodului R Traversrile n inordine ale subarborilor A2, A3,...,Ak.
3o. Traversarea n postordine a arborelui A const n:
Traversarea n postordine a subarborilor A1, A2, ....,Ak Traversarea nodului R.
Structurile de principiu ale procedurilor care realizeaz aceste traversri apar n secvena [8.1.3.1.a] iar un exemplu de implementare generic n secvena [8.1.3.1.b].
-
----------------------------------------------------------- {Traversarea arborelui generalizat - modalii principiale} Preordine(A) :R,Preordine(A1),Preordine(A2),..., Preordine(Ak). Inordine(A) :Inordine(A1),R,Inordine(A2),..., Inordine(Ak). [8.1.3.1.a] Postordine(A):Postordine(A1), Postordine(A2),..., Postordine(Ak),R. ----------------------------------------------------------- {Traversarea n Preordine a arborelui generalizat} procedure Preordine(r: TipNod); *listeaza(r); pentru fiecare fiu f al lui r,(dac exist vreunul), n ordine de la stnga spre dreapta execut Preordine(f); ---------------- ------------------------------------- --------{Traversarea n Inordine a arborelui generalizat} procedure Inordine(r: TipNod); dac *r este nod terminal atunci *listeaz(r); altfel [8.1.3.1.b] Inordine(cel mai din stnga fiu al lui r); *listeaz(r); pentru fiecare fiu f al lui r, cu excepia celui mai din stnga, n ordine de la stnga spre dreapta execut Inordine(f); ------------------------------------------------------------- {Traversarea n Postordine a arborelui generalizat} procedure Postordine(r: TipNod); pentru fiecare fiu f al lui r,(dac exist vreunul), n ordine de la stnga spre dreapta execut Postordine(f); *listeaza(r); -------------------------------------------------------------
-
Spre exemplu pentru arborele din figura 8.1.3.1.b (a), traversrile anterior definite, conduc la urmtoarele secvene de noduri:
preordine: 1,2,3,5,8,9,6,10,4,7. postordine: 2,8,9,5,10,6,3,7,4,1. inordine: 2,1,8,5,9,3,10,6,7,4.
1
2 4
7
3
6 5
10 9 8
1
2 4
7
3
6 5
10 98
(a) (b)
Fig.8.1.3.1.b. Traversarea unui arbore generalizat
O metod practic simpl de parcurgere a unui arbore este urmtoarea:
Dndu-se o structur de arbore generalizat, se imagineaz parcurgerea acesteia n sens trigonometric pozitiv, rmnnd ct mai aproape posibil de arbore (fig.8.1.3.1.b (b)).
Pentru preordine, nodurile se listeaz de prima dat cnd sunt ntlnite: 1, 2, 3, 5, 8, 9, 6, 10, 4, 7;
Pentru postordine nodurile se listeaz ultima dat cnd sunt ntlnite, respectiv cnd sensul de parcurgere este spre prinii lor: 2, 8, 9, 5, 10, 6, 3, 7, 4, 1;
Pentru inordine, un nod terminal se listeaz cnd este ntlnit prima oar, iar un nod interior cnd este ntlnit a doua oar: 2, 1, 8, 5, 9, 3, 10, 6, 7, 4.
------------------------------------------------------------ Exemplul 8.1.3.1.a. Implementarea traversrii n preordine a unui arbore utiliznd operatorii definii n cadrul TDA Arbore generalizat, varianta recursiv.
Procedura din secvena urmtoare realizeaz tiprirea n preordine a cheilor nodurilor arborelui generalizat A
Procedura este apelat prin urmtorul apel: TraversarePreordine(Radacina(A)).
Se presupune c nodurile arborelui sunt de tip TipNod.
-----------------------------------------------------------
-
PROCEDURE TraversarePreordine(r: TipNod); {Implementare bazat pe setul de operatori TDA Arbore generalizat} {listeaza cheile descendentilor lui r in preordine} VAR f: TipNod; BEGIN Write(Cheie(r,a)); f:=PrimulFiu(r,a); WHILE f0 DO BEGIN [8.1.3.1.c] TraversarePreordine(f); f:=FrateDreapta(f,a) END END; {Preordine} ----------------------------------------------------------- Exemplul 8.1.3.1.b. Implementarea traversrii n preordine a unui arbore utiliznd operatorii definii n cadrul TDA Arbore generalizat, varianta nerecursiv.
Se presupune c nodurile arborelui sunt de tip TipNod.
n cadrul variantei nerecursive se utilizeaz stiva s, care conine elemente de TipNod.
Cnd se ajunge la prelucrarea nodului n, stiva va conine memorat drumul de la rdcin la nodul n, cu rdcina la baza stivei i nodul n n vrf.
Procedura care apare n secvena [8.1.3.1.d], are dou moduri de aciune.
(1) n primul mod, se descinde de-a lungul celui mai stng drum neexplorat din cadrul arborelui, tiprind (prelucrnd) nodurile ntlnite pe drum i introducndu-le n stiv, pn se ajunge la un nod terminal.
(2) n acest moment se trece n cel de-al doilea mod de operare care presupune revenirea pe drumul memorat n stiv, eliminnd pe rnd nodurile, pn la ntlnirea primului nod care are frate drept.
n acest moment se revine n primul mod i rencepe descinderea cu acest frate nc neexplorat.
Procedura ncepe n modul unu i se termin cnd stiva devine vid.
------------------------------------------------------------- PROCEDURE TraversarePreordineNerecursiva(a: TipNod); {Implementare nerecursiva bazata pe structura stiva} {Se utilizeaz operatorii TDA Arbore generalizat, TDA Stiva} VAR m: TipNod; s: TipStiva; gata: boolean; BEGIN Initializeaz(s); m:=Radacina(a); gata:=false; WHILE NOT gata DO
-
IF m0 THEN BEGIN Write(Cheie(m,a)); Push(m,s); m:=PrimulFiu(m,a) {exploreaz fiul stng} END ELSE IF Stivid(s) THEN gata:=true [8.1.3.1.d] ELSE BEGIN m:=FrateDreapta(VarfSt(s),a); Pop(s) END END; {TraversarePreordineNerecursiva} ------------------------------------------------------------
8.1.3.2. Traversarea arborilor generalizai prin tehnica cutrii prin cuprindere
Tehnica cutrii prin cuprindere deriv tot din traversarea grafurilor, dar ea este utilizat, e adevarat mai rar, i la traversarea arborilor [Ko86].
Se mai numete i traversare pe niveluri (level traversal) [We94] i este utilizat cu precdere n reprezentarea grafic a arborilor.
Principiul acestei tehnici este simplu: nodurile nivelului i+1 al structurii arbore sunt vizitate doar dup ce au fost vizitate toate nodurile nivelului i (0
-
Exemplul 8.1.3.2. Implementarea traversrii prin cuprindere a unui arbore utiliznd operatorii definii n cadrul TDA Arbore generalizat i TDA Coad este ilustrat n secvena [8.1.3.2.b]. Nodurile vizitate sunt afiate. ------------------------------------------------------------- PROCEDURE TraversarePrinCuprindere(r: TipNod); {Implementare bazat pe TDA Arbore generalizat, TDA Coada} VAR Coada: TipCoada; f: TipNod; BEGIN Initializeaza(Coada); Adauga(r,Coada); WHILE NOT Vid(Coada) DO BEGIN r:=Cap(Coada); Scoate(Coada); WRITE(Cheie(r)); f:=PrimulFiu(r); IF f NIL THEN [8.1.3.2.b] BEGIN Adauga(f,Coada); f:=FrateDreapta(f) WHILE f NIL DO BEGIN Adauga(f,Coada); f:=FrateDreapta(f) END END END END;{TraversarePrinCuprindere} ------------------------------------------------------------
8.1.4. Tehnici de implementare a TDA arbore generalizat
n cadrul acestui subcapitol se vor prezenta cteva din implementrile posibile ale structurii arbore generalizat, corelate cu aprecieri referitoare la capacitatea acestora de a suporta operatorii definii n cadrul TDA Arbore generalizat.
8.1.4.1. Implementarea arborilor generalizai cu ajutorul tablourilor
Se bazeaz pe urmtoarea metod:
Fie A un arbore generalizat cu n noduri.
Se numeroteaz nodurile arborelui A de la 1 la n.
Se asociaz nodurilor arborelui elementele unui tablou A, astfel nct nodului i al arborelui i corespunde locaia A[i] din tablou.
Cea mai simpl manier de reprezentare a unui arbore, care permite implementarea operaiei Tata, este cea conform creia fiecare intrare A[i] din tablou memoreaz un indicator (cursor) la printele nodului i.
Rdcina se poate distinge prin valoarea zero a cursorului.
-
Cu alte cuvinte, dac A[i] = j atunci nodul j este printele nodului i iar dac A[i]= 0, atunci nodul i este rdcina arborelui.
Acest mod de reprezentare, face uz de proprietatea arborilor care stipuleaz c orice nod are un singur printe, motiv pentru care se numete i "indicator spre printe".
Gsirea printelui unui nod se face ntr-un interval constant de timp O(1) iar parcurgerea arborelui n direcia nod - printe, se realizeaz ntr-un interval de timp proporional cu adncimea nodului.
Chei
1 2 3 4 5 6 7 8 9 10
r b c d e h i j f g
1 2 3 4 5 6 7 8 9 10
A 0 1 1 2 2 5 5 5 3 3
(10) (9)
(8) (7) (6)
(5) (4)
(3) (2)
(1)
c b
g f d e
j i h
r
(a) (b)
Fig. 8.1.4.1.a. Reprezentarea arborilor generalizai cu ajutorul tablourilor (varianta indicator spre printe)
Aceast reprezentare poate implementa simplu i operatorul Cheie dac se adaug un alt tablou Chei, astfel nct Chei[i] este cheia nodului i, sau dac elementele tabloului A se definesc de tip articol avnd cmpurile cheie i cursor.
n figura 8.1.4.1.a apare o astfel de reprezentare (b) a aborelui generalizat (a).
Reperezentarea "indicator spre printe" are ns dezavantajul implementrii dificile a operatorilor referitori la fii.
Astfel, unui nod dat n, i se determin cu dificultate fiii sau nlimea.
n plus, reprezentarea "indicator spre printe", nu permite specificarea ordinii fiilor unui nod, astfel nct operatorii PrimulFiu i FrateDreapta nu sunt bine precizai.
Pentru a da acuratee reprezentrii, se poate impune o ordine artificial a nodurilor n tablou, respectnd urmtoarele convenii:
(a) - numerotarea fiilor unui nod se face numai dup ce nodul a fost numrat;
(b) - numerele fiilor cresc de la stnga spre dreapta. Nu este necesar ca fiii s
ocupe poziii adiacente n tablou.
n accepiunea respectrii acestor convenii, n secvena [8.1.4.1.a] apare redactat funcia FrateDrepta.
-
Tipurile de date presupuse sunt cele precizate n antetul procedurii. Se presupune c nodul vid este reprezentat prin zero.
------------------------------------------------------------- {Implementarea Arborilor generalizai cu ajutorul tablourilor varianta Indicator spre printe} TYPE TipNod=integer; TipArbore=ARRAY[1..maxnod] OF TipNod; {Exemplu de implementare a operatorului FrateDreapta} FUNCTION FrateDreapta(n: TipNod; a: TipArbore): TipNod; VAR i,parinte: TipNod; BEGIN parinte:=a[n]; [8.1.4.1.a] FrateDreapta:=0; i:=n; REPEAT i:=i+1; IF a[i]=parinte THEN FrateDreapta:=i UNTIL(FrateDreapta0) OR (i=maxnod) END;{FrateDreapta} ------------------------------------------------------------- 8.1.4.2. Implementarea arborilor generalizai cu ajutorul listelor
O manier important i util de implementare a arborilor generalizai este aceea de a crea pentru fiecare nod al arborelui o list a fiilor si.
Datorit faptului c numrul fiilor poate fi variabil, o variant potrivit de implementare o reprezint utilizarea listelor nlnuite.
n fig.8.1.4.2.a se sugereaz maniera n care se poate implementa arborele din figura 8.1.4.1.a.(a).
Se utilizeaz un tablou (inceput) care conine cte o locaie pentru fiecare nod al arborelui.
Fiecare element al tabloului inceput este o referin la o list nlnuit simpl, ale crei elemente sunt nodurile fii ai nodului corespunztor intrrii, adic elementele listei indicate de inceput[i] sunt fiii nodului i.
radacina
MaxNod
inceput
indice urm
3 Nil
7
5 Nil
10 Nil
8 Nil 6
1
1 2 3 4 5 6 7 8 9 10
r b c d e h i j f g
1 2 3 4 5 6 7 8 9 10
Nil Nil Nil Nil Nil Nil
9
2
4
chei
-
Fig.8.1.4.2.a. Reprezentarea arborilor generalizai cu ajutorul listelor nlnuite .
n continuare se prezint un exemplu de implementare utiliznd liste nlnuite simple bazate pe pointeri
Tipurile de date propuse apar n secvena [8.1.4.2.a].
Se presupune c rdcina arborelui este memorat n cmpul specific radacina.
Nodul vid se reprezint prin valoarea NIL.
n aceste condiii n secvena [8.1.4.2.b] apare implementarea operatorului PrimulFiu.
Se presupune c se utilizeaz operatorii definii peste tipul de date abstract list prezentai n Vol. 1, &6.2.1
------------------------------------------------------------ {Reprezentarea arborilor generalizai utiliznd liste nlnuite simple implementate cu ajutorul pointerilor} TYPE TipPointreNod=^TipNodList; TipNodList=RECORD indice:1..MaxNod; urm :TipPointerNod END; TipNod=0..MaxNod; [8.1.4.2.a] TipLista=TipPointerNod; TipArbore=RECORD inceput:ARRAY[1..MaxNod] OF TipLista; {chei:ARRAY[1..MaxNod] OF TipCheie;} radacina:TipNod END; ------------------------------------------------------------- {Exemplu de implementare al operatorului PrimulFiu} {se utilizeaz TDA List, varianta restrns} FUNCTION PrimulFiu(n: TipNod; a: TipArbore): TipNod; VAR l: TipLista; BEGIN l:=a.inceput[n]; [8.1.4.2.b] IF Fin(l) THEN {n este un nod terminal} mulFiu:=0 Pri ELSE PrimulFiu:=Furnizeaza(Primul(l),l) END;{PrimulFiu} ------------------------------------------------------------- 8.1.4.3. Implementarea structurii arbore generalizat pe baza relaiilor "primul-fiu" i "frate-dreapta"
Implementrile structurilor de arbori generalizai, descrise pn n prezent, printre alte dezavantaje, l au i pe acela de a nu permite implementarea simpl a operatorului Creaza i deci de a nu permite dezvoltarea facil a unor structuri complexe pornind de la structuri simple.
-
Pentru a rezolva aceast problem, pentru implementarea structurii arbore genearlizat se poate utiliza o structur ca cea din figura 8.1.4.3.b, n forma tabloului Zona care are urmtoarele caracteristici:
Fiecare nod al arborelui este identificat prin indexul celulei pe care el o ocup n tabloul Zona
Alocarea nodurilor se realizeaz n manier dinamic utiliznd locaia Disponibil. Nodurile disponibile se nlnuie prin intermediul cmpului primulFiu
Cmpul frateDreapta indic fratele dreapta al nodului respectiv
Cmpul primulFiu indic primul fiu al nodului respectiv
Cmpul tata indic printele nodului respectiv
primulFiu cheie frateDreapta tata
Fig.8.1.4.3.b. Reprezentarea unui arbore generalizat cu ajutorul relaiilor primul-fiu i frate-dreapta (Varianta 2)
O structur de date ncadrat n TipArbore, este desemnat n aceste condiii printr-un indice n tabloul Zona, indice care indic nodul rdcin al arborelui.
n fig.8.1.4.3.b, apare reprezentarea arborelui din figura 8.1.4.3.a., iar n secvena [8.1.4.3.b] apare definiia formala a structurii de date corespunztoare acestui mod de implementare al arborilor generalizai.
------------------------------------------------------------{Reprezentarea arborilor generalizai bazat pe relaiile primul-fiu i frate-dreapta (Varianta 2)} TYPE TipCursor=0..MaxNod; TipArbore=TipCursor; [8.1.4.3.b] VAR Zona:ARRAY[1..MaxNod] OF RECORD primulFiu:TipCursor;
2 5 7 10 11 MaxNod
R
Disponibil
e 7 b 11 10 2 d 10 5 a c 7 10
Zona
-
cheie:TipCheie; frateDreapta:TipCursor; tata:TipCursor END; Disponibil:TipCursor; R:TipArbore; -------------------------------------------------------------
n secvena [8.1.4.3.c] este prezentat un exemplu de implementare a operatorului Creaza2, pornind de la reprezentarea propus.
Se reamintete c exist o list a liberilor n tabloul Zona, indicat prin cursorul Disponibil, n cadrul creia elementele sunt nlnuite prin intermediul cmpului primulFiu.
------------------------------------------------------------- {Exemplu de implementare al operatorului Creaza2} FUNCTION Creaza2(v:TipCheie; t1,t2:TipArbore):TipArbore; VAR temp:TipCursor; {pastreaza indexul primei locatii disponibile pentru radacina noului arbore} BEGIN temp:=Disponibil; Disponibil:=Zona[Disponibil].frateDreapta; Zona[temp].primulFiu:=t1; [8.1.4.3.c] Zona[temp].cheie:=v; Zona[temp].frateDreapta:=0; Zona[temp].tata:=0; Zona[t1].frateDreapta:=t2; Zona[t1].tata:=temp; Zona[t2].frateDreapta:=0; Zona[t2].tata:=temp; C END; {Creaza2}
reaza2:=temp
------------------------------------------------------------- 8.2. Arbori binari 8.2.1. Definiii
Prin arbore binar se nelege o mulime de n 0 noduri care dac nu este vid, conine un anumit nod numit rdcin, iar restul nodurilor formeaz doi arbori binari disjunci numii: subarborele stng respectiv subarborele drept.
Ca i exemple pot fi considerai arborii binari reprezentai n figura 8.2.1.a.
a a aa
bbc bb c
(a) (b) (c) (d)
Fig.8.2.1.a. Structuri de arbori binari
-
Structurile (a) i (b) din fig.8.2.1.a. dei conin noduri identice, reprezint arbori binari diferii deoarece se face o distincie net ntre subarborele stng i subarborele drept al unui arbore binar.
Acest lucru este pus i mai pregnant n eviden de structurile (c) i (d) din fig.8.2.1.a. care de asemenea reprezint arbori diferii.
O expresie aritmetic obinuit poate fi reprezentat cu ajutorul unui arbore binar ntruct operatorii aritmetici sunt operatori binari..
Spre exemplu, pentru expresia (a+b/c)*(d-e*f), arborele binar corespunztor care se mai numete i arbore de parcurgere (parse tree), apare n figura 8.2.1.b.
(1)*
-+
*d/ a
fecb
(2) (3)
(4) (5)(9)
(7)
(6)
(11)(10)(8)
Fig.8.2.1.b. Arbore binar asociat unei expresii aritmetice
Structura arbore binar este deosebit de important deoarece: (1) Pe de o parte este uor de reprezentat i prelucrat, bucurndu-se de o serie de proprieti specifice, (2) Pe de alt parte, orice structur de arbore, poate fi transformat ntr-o structur de arbore binar.
8.2.2. Tehnica transformrii unei structuri de arbore generalizat ntr-o structur de arbore binar.
Fie un arbore generalizat oarecare A, care are rdcina A1 i subarborii A11, A12...,A1k.
Transformarea acestuia ntr-un arbore binar se realizeaz dup cum urmeaz:
Se ia A1 drept rdcin a arborelui binar,
Se face subarborele A11 fiul su stng,
Apoi fiecare subarbore A1i se face fiul drept al lui A1,i-1 pentru 2ik.
-
Se continu n aceeai manier transformnd dup acelai algoritm fiecare din subarborii rezultai, pn la parcurgerea integral a arborelui iniial.
Grafic, aceast tehnic apare reprezentat n figura 8.2.2.a, (a)-cazul general i (b)-un exemplu.
A11
A12 ... A1k
A1
A11B
A
IHGFE
DC
J
A1k
A1
A12
I
CE
B
A
J
H
DGF
(a) (b)
Fig.8.2.2.a. Transformarea unui arbore oarecare n arbore binar 8.2.3. TDA Arbore binar
Tipul de date abstract arbore binar, ca de altfel orice TDA presupune:
(1) Definirea modelului matematic asociat structurii arbore binar
(2) definirea setului de operatori care gestioneaz structura.
Ca i n cadrul altor TDA-uri, este greu de stabilit un set de operatori care s ofere satisfacie n toate clasele de aplicaii posibile.
n cadrul cursului de fa se propune pentru TDA Arbore binar forma prezentat n [8.2.3.a].
------------------------------------------------------------ TDA Arbore binar
-
Modelul matematic: o structur de noduri. Toate nodurile sunt
de acelai tip. Fiecare nod este rdacina unui subarbore i este alctuit din trei cmpuri: element, indicator stng i indicator drept. Indicatorii precizeaz subarborele stng respectiv subarborele drept al subarborelui n cauza. n cadrul cmpului element poate exista un cmp cheie care identific nodul.
Notaii: TipNod - tipul asociat nodurilor arborelui TipArboreBinar - tipul arbore binar TipIndicatorNod - indicator la nod t,s,d: TipArboreBinar; r,n: TipIndicatorNod; w: TipNod; b: boolean; [8.2.3.a] Operatori: 1. CreazaArboreVid(t: TipArboreBinar); - procedur care
creaz arborele vid t; 2. ArboreVid(t: TipArboreBinar): boolean; - funcie care
returneaz valoarea adevrat dac arborele t este vid i fals n caz contrar.
3. Radacina(n: TipIndicatorNod ): TipIndicatorNod; -
returneaz indicatorul rdcinii arborelui binar cruia i aparine nodul n;
4. Parinte(n: TipIndicatorNod, t:TipArboreBinar)
:TipIndicatorNod; - returneaz indicatorul Printelui(tatlui) nodului n aparinnd arborelui t;
5. FiuStanga(n: TipIndicatorNod,t:TipArboreBinar)
:TipIndicatorNod; - returneaz indicatorul fiului stng al nodului n aparinnd arborelui t;
6. FiuDreapta(n: TipIndicatorNod,t: TipArboreBinar):
TipIndicatorNod; - returneaz indicatorul fiului drept al nodului n aparinnd arborelui t;
7. SuprimaSub(n: TipIndicatorNod,t: TipArboreBinar); -
suprim subarborele a crui radacin este nodul n, aparinnd arborelui binar t;
8. InlocuiesteSub(n: TipIndicatorNod, r,t: TipArboreBinar); -
insereaz arborele binar r n t, cu rdacina lui r localizat n poziia nodului n, nlocuind subarborele indicat de n. Operatorul se utilizeaz de regul cnd n este o frunz a lui t, caz n care poate fi asimilat cu operatorul adaug;
9. Creaza2(s,d: TipArboreBinar,r: TipIndicatorNod):
TipArboreBinar; - creaz un arbore binar nou care are
-
nodul r pe post de rdcin i pe s i d drept subarbore stng respectiv subarbore drept
10. Furnizeaza(n: TipIndicatorNod,t: TipArboreBinar):
TipNod; - returneaz coninutul nodului indicat de n din arborele binar t. Se presupune c n exist n t;
11. Actualizeaza(n: TipIndicatorNod, w: TipNod, t:
TipArboreBinar); - nlocuiete coninutul nodului indicat de n din t cu valorea w. Se presupune c n exist.
12. Cauta(w: TipNod, t: TipArboreBinar): TipIndicatorNod;
returneaz indicatorul nodului aparinnd arborelui binar t, al crui coninut este w;
13. Preordine(t: TipArboreBinar,Vizitare(listaArgumente)); -
operator care realizeaz parcurgerea n preordine a arborelui binar t aplicnd fiecrui nod, procedura Vizitare;
14. Inordine(t: TipArboreBinar, Vizitare(listaArgumente)); -
operator care realizeaz parcurgerea n inordine a arborelui binar t aplicnd fiecrui nod, procedura Vizitare;
15. Postordine(t:TipArboreBinar,Vizitare(listaArgumente)); -
operator care realizeaz parcurgerea n postordine a arborelui binar t aplicnd fiecrui nod, procedura Vizitare.
------------------------------------------------------------- 8.2.4. Tehnici de implementare a arborilor binari
n aplicaiile curente se utilizeaz dou modaliti de implementare a structurii arbore binar:
(1) Implementarea bazat pe tablouri (mai rar utilizat)
(2) Implementarea bazat pe pointeri.
8.2.4.1. Implementarea arborilor binari cu ajutorul structurii tablou
Pentru implementarea unui arbore binar se poate utiliza o structur de tablou liniar definit dup cum urmeaz [8.2.4.1.a]:
------------------------------------------------------------- {Implementarea unui arbore binar cu ajutorul unei structuri de tablou liniar}
-
TYPE TipCursor=0..MaxNod; TipElement=RECORD Op:char; [8.2.4.1.a] stang,drept:TipCursor END; TipArbore=ARRAY[TipCursor] OF TipElement; VAR T:TipArbore; ------------------------------------------------------------
n prealabil fiecrui nod al arborelui i se asociaz n mod aleator o intrare n tabloul liniar.
n principiu, acesta este o implementare bazat pe cursori.
n fig.8.2.4.1.a apare o astfel de reprezentare a unui arbore binar.
Op stang drept
(11)
(1) *
- +
*d / a
fe c b
(2) (3)
(4) (5) (9)
(7)
(6)
(10) (8)
1 * 2 3 2 + 6 4 3 - 9 5 4 / 7 8 5 * 10 11 6 a 0 0 7 b 0 0 8 c 0 0 9 d 0 0 10 e 0 0 11 f 0 0
Fig.8.2.4.1.a. Reprezentarea unui abore binar cu ajutorul unui tablou liniar
Un alt mod de reprezentare cu ajutorul structurilor de tip tablou se bazeaz pe urmtoarele dou leme.
Lema 1. Numrul maxim de noduri al nivelului i al unui arbore binar este 2i-1.
Ca atare, numrul maxim de noduri al unui arbore de nlime h este [8.2.4.1.b].
-------------------------------------------------------------
=
>==h
i
hiNrMax1
1 122 ][8.2.4.1.b 0h pentru -------------------------------------------------------------
Arborele binar de nlime h care are exact 2h-1 noduri se numete arbore binar plin de nlime h.
Dac se numeroteaz secvenial nodurile unui arbore binar plin de nlime h, ncepnd cu nodul situat pe nivelul 1 i continund numrtoarea nivel cu nivel de sus n jos, i n cadrul fiecrui nivel, de la stnga la dreapta;
Se poate realiza o implementare elegant a structurii de arbore binar, asociind fiecrui nod al arborelui, locaia corespunztoare numrului su ntr-un tablou liniar (fig.8.2.4.1.b .).
-
A
C
ONMLKJ I H
B
GFED
8 9 10 11 12 13 14 15
4 5 6 7
2 3
1
Arbore 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E F G H I J K L M N O Fig.8.2.4.1.b. Arbore binar plin i reprezentarea sa cu ajutorul unui tablou liniar
Lema urmtoare precizeaz maniera deosebit de simpl n care se poate determina printele, fiul stng i fiul drept al unui nod precizat, fr memorarea explicit a nici unui fel de informaie de legtur.
Lema 2. Dac se reprezint un arbore binar plin ntr-o manier conform cu cele anterior precizate, atunci pentru orice nod avnd indicele i,1in sunt valabile relaiile:
1. Parinte(i) este nodul avnd indicele i/2 dac i1. Dac i=1 nodul indicat de i este nodul rdcin care nu are printe.
2. FiuStanga(i) este nodul avnd indicele 2*i dac 2*in. Dac 2*i>n, atunci nodul i nu are fiu stng.
3. FiuDreapta(i) este nodul avnd indicele 2*i+1 dac 2*i+1n. Dac 2*i+1>n, atunci nodul i nu are fiu drept.
Acest mod de implementare poate fi n mod evident utilizat pentru orice structur de arbore binar, n marea majoritate a cazurilor rezultnd ns o utilizare ineficient a zonei de memorie alocate tabloului.
Spre exemplu n fig.8.2.4.1.d apare reprezentarea arborelui binar din fig.8.2.4.1.a. n acest caz se fac urmtoarele precizri:
h este cea mai mic nime de arbore binar plin care "cuprinde" arborele n cauz;
Se numeroteaz i nodurile lips ale arborelui de reprezentat, ele fiind nlocuite cu nodul vid n cadrul reprezentrii.
-
*
-+
*d/a
fecb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
* + - a / d * b c e f
Fig.8.2.4.1.d. Reprezentarea secvenial a unui arbore binar oarecare
Se remarc similitudinea dintre acest mod de reprezentare i reprezentarea ansamblelor (Vol.1 &3.2.5).
Aceast manier de reprezentare a arborilor binari sufer de neajunsurile specifice reprezentrii bazate pe tablouri liniare:
Inseria sau suprimarea unui nod trebuie s fie nsoit de schimbarea poziiei unor noduri din tablou, astfel nct acesta s reflecte modificrile survenite prin poziiile nodurilor rmase.
Concluzionnd, referitor la aceast manier de implementare a arborilor binari se pot face urmtoarele precizri:
Avantaje: Simplitate, absena legturilor; parcurgerea simpl a arborelui n ambele sensuri.
Dezavantaje: Implementarea complicat a modificrilor (inserii, suprimri).
Se recomand: n cazul arborilor binari cu o dinamic redus a modificrilor, n care se realizeaz multe parcurgeri sau cautri.
8.2.4.2. Implementarea arborilor binari cu ajutorul pointerilor
Maniera cea mai natural i cea mai flexibil de reprezentare a arborilor binari este cea bazat pe TDA Indicator.
Acest mod de reprezentare are dou avantaje:
Pe de-o parte nltur limitrile reprezentrii secveniale bazate pe structura tablou
-
Pe de alt parte face uz de proprietile recursive ale structurii arbore, implementarea realizndu-se cu ajutorul structurilor de date dinamice.
Un arbore binar poate fi descris cu ajutorul unei structuri de date dinamice n variant Pascal (secvena [8.2.4.2.a]) respectiv n variant C (secvena [8.2.4.2.b]).
------------------------------------------------------------ {Implementarea arborilor binari cu ajutorul pointerilor} TYPE RefTipNod=^TipNod; TipNod=RECORD cheie:char; [8.2.4.2.a] stang,drept: RefTipNod END; TipArboreBinar= RefTipNod; ------------------------------------------------------------- // implementare C typedef struct nod { //diferite campuri char cheie; struct nod* stang; [8.2.4.2.b] struct nod* drept; }NOD; ------------------------------------------------------------
n fig.8.2.4.2.a se poate urmri reprezentarea arborelui binar din figura 8.2.4.1.a bazat pe definiia din secvena [8.2.4.2.a.].
Este uor de vzut c practic orice arbore poate fi reprezentat n acest mod.
n cadrul cursului de fa, aceast modalitate de reprezentare va fi n mod preponderent utilizat.
(11)
(1)*
-+
*d/a
fecb
(2) (3)
(4) (5) (9)
(7)
(6)
(10) (8)
-
* /
- +
*
f nil nil
Radacina
d nil nil
b nil nil
a nil nil
e nil nil
c nil nil
Fig.8.2.4.2.a. Arbore binar reprezentat cu ajutorul pointerilor 8.2.5. Traversarea arborilor binari
Referitor la tehnicile de traversare a arborilor binari se face precizarea c ele
deriv direct prin particularizare din tehnicile de traversare a arborilor generalizai.
n consecin i n acest caz se disting tehnicile bazate pe cutarea n adncime
(preordine, inordine i postordine) precum i tehnica cutrii prin cuprindere.
8.2.5.1. Traversarea arborilor binari prin tehnici bazate pe cutarea n adncime
Traversarea n adncime (depth first), aa cum s-a precizat i n cadrul arborilor generalizai, presupune parcurgerea n adncime a arborelui binar att de departe ct se poate plecnd de la rdcin.
Cnd s-a ajuns la o frunz, se revine pe drumul parcurs la proximul nod care are
fii neexplorai i parcurgerea se reia n aceeai manier pn la traversarea integral a structurii.
Schema este bun dar presupune memorarea drumului parcurs, ca atare necesit
fie o implementare recursiv fie utilizarea unei stive.
Traversarea n adncime are trei variante: preordine, inordine i postordine.
Considerentele avute n vedere la traversarea arborilor generalizai rmn valabile i pentru arborii binari.
Astfel, referindu-ne la arborele binar din fig.8.2.5.1.a i considernd pe R drept
rdacin, iar pe SS i SD drept subarborele su stng, respectiv subarborele su drept, atunci cele trei moduri de parcurgere sunt evideniate de modelele recursive din secvena [8.2.5.1.a].
------------------------------------------------------------
-
{Modele recursive pentru traversarea arborilor binari prin tehnica cutrii n adncime} Preordine(A) : R,Preordine(SS),Preordine(SD) Inordine(A) : Inordine(SS),R,Inordine(SD) [8.2.5.1.a] Postordine(A): Postordine(SS),Postordine(SD),R ------------------------------------------------------------
R
SS SD
Fig.8.2.5.1.a. Model de arbore binar
Traversarea unei structuri de date este de fapt o ordonare liniar a componentelor sale n baza unui anumit protocol.
Spre exemplu, traversnd arborele care memoreaz expresia aritmetic
(a+b/c)*(d-e*f) din fig.8.2.1.b i nregistrnd caracterul corespunztor ori de cte ori este vizitat un nod se obin urmtoarele ordonri:
(11)
(1)*
-+
*d/a
fecb
(2) (3)
(4) (5) (9)
(7)
(6)
(10) (8)
Preordine: *+a/bc-d*ef Inordine: a+b/c*d-e*f Postordine: abc/+def*-*
Se precizeaz faptul c ultima ordonare este cunoscut n matematic sub
denumirea de notaie polonez (postfix).
n continuare, cele trei metode de traversare vor fi concretizate n trei proceduri recursive n care:
o r este o variabil de tip pointer care indic rdcina arborelui
o Viziteaza(r^) reprezint operaia care trebuie executat asupra
fiecrui nod.
-
Considernd pentru structura de arbore binar definiia din secvena [8.2.5.1.b], structura de principiu a celor trei metode de traversare este prezentat n [8.2.5.1.c].
------------------------------------------------------------- {Traversarea arborilor binari} TYPE RefTipNod=^TipNod; TipNod=RECORD {diferite cmpuri} [8.2.5.1.b] stang,drept:RefTipNod END; ------------------------------------------------------------- PROCEDURE Preordine(r:RefTipNod); BEGIN IF rnil THEN BEGIN Viziteaza(r^); Preordine(r^.stang); Preordine(r^.drept) END END; {Preordine} PROCEDURE Inordine(r:RefTipNod); BEGIN IF rnil THEN BEGIN Inordine(r^.stang); [8.2.5.1.c] Viziteaza(r^); Inordine(r^.drept) END END; {Inordine} PROCEDURE Postordine(r:RefTipNod); BEGIN IF rnil THEN BEGIN Postordine(r^.stang); Postordine(r^.drept); Viziteaza(r^) END END; {Postordine} ------------------------------------------------------------------------ 8.2.5.2. Traversarea arborilor binari prin tehnica cutrii prin cuprindere
Traversarea prin cuprindere (breadth-first) presupune traversarea tuturor nodurilor de pe un nivel al structurii arborelui, dup care se trece la nivelul urmtor parcurgndu-se nodurile acestui nivel .a.m.d pn la epuizarea tuturor nivelurilor arborelui.
n cazul arborilor binari, rmne valabil schema de principiu a parcurgerii prin
cuprindere bazat pe utilizarea unei structuri de date coad prezentat pentru arborii generalizai (secvena [8.1.3.2.a]) cu precizarea c nodurile pot avea cel mult doi fii.
n continuare se prezint o alt variant de parcurgere care permite efectiv
-
evidenierea nivelurilor arborelui binar, variant care utilizeaz n tandem dou structuri de tip coad (secvena [8.2.5.2.a]).
o La parcurgerea nodurilor unui nivel al arborelui binar, noduri care sunt
memorate ntr-una din cozi, fiii acestora se adaug celeilalte cozi. o La terminarea unui nivel (golirea cozii curente parcurse), cozile sunt
comutate i procesul se reia pn la parcurgerea integral a arborelui binar, adic golirea ambelor cozi.
------------------------------------------------------------ {Traversarea prin cuprindere unui arbore binar cu evidenierea nivelurilor acestuia} procedure TraversarePrinCuprindereArboreBinar(r: TipNod) Coada1, Coada2: TipCoada; Initializeaza(Coada1); Initializeaza(Coada2); daca r nu este nodul vid atunci Adauga(r,Coada1); {procesul de amorsare} repet ct timp NOT Vid(Coada1)execut r
-
Pentru aceasta este necesar ca fiecrui nivel al structurii s-i fie alocate numrul maxim de noduri posibile, cu excepia nivelului de baz.
Acest lucru poate fi realizat prin distribuirea n mod egal a nodurilor care se
introduc n structur pe stnga respectiv pe dreapta fiecrui nod deja introdus.
Regula dup care se asigur distribuia egal pentru un numr cunoscut de noduri n poate fi formulat simplu n termeni recursivi:
1o Se ia un nod drept rdcin; 2o Se genereaz subarborele stng cu ns=n DIV 2 noduri; 3o Se genereaz subarborele drept cu nd=n-ns-1 noduri.
Acest algoritm, permite construcia simpl a unui arbore binar de nalime minim. Un arbore binar este considerat perfect echilibrat dac pentru fiecare nod,
numrul de noduri al subarborelui stng difer de cel al subarborelui drept cu cel mult o unitate.
n mod evident c arborele de nalime minim construit de ctre acest algoritm
este unul perfect echilbrat.
Implementarea algoritmului varianta C apare n secvena [8.2.7.1.a].
o Cheile nodurilor se introduc de la tastatur. o Prima valoare introdus este numrul total de noduri n.
o Sarcina construciei efective a arborelui binar revine funciei Arbore care:
Primete ca parametru de intrare numrul de noduri n, Determin numrul de noduri pentru cei doi subarbori, Citete cheia nodului rdcin, Construiete n manier recursiv arborele, Returneaz referina la arborele binar construit.
------------------------------------------------------------ //Construcie arbore binar de nlime minim #include #include #include typedef struct nod [8.2.7.1.a] { int cheie; struct nod* stang; struct nod* drept; }NOD; int n; NOD* radacina; NOD* Arbore( int n )
-
{ //constructie arbore perfect echilibrat cu N noduri NOD* NodNou; int x, ns, nd; if ( n == 0 ) return NULL; ns = n / 2; [8.2.7.1.a] nd = n - ns - 1; scanf( "%d", &x ); //citete coninut nod if ( ( NodNou = (NOD *)malloc( sizeof( NOD ) ) ) == NULL ) { printf("Eroare la malloc"); return NULL; } NodNou->cheie = x; NodNou->stang = Arbore( ns ); //completare nlnuire NodNou->drept = Arbore( nd ); //completare nlnuire return NodNou; }//Arbore void Afiseaza_Arbore( NOD* t, int h) { //afiseaza arborele t int i; if ( t != NULL ) { Afiseaza_Arbore( t->stang, h - 5 ); for(i = 0; i < h; i++) printf( " " ); printf( "%d\r\n", t->cheie ); Afiseaza_Arbore( t->drept, h - 5 ); }//if }//Afiseaza_Arbore int main( int argc, char** argv ) { printf( "n=" ); scanf("%d", &n); //citete numrul total de noduri radacina = Arbore( n ); Afiseaza_Arbore( radacina, 50 ); return 0; }//main -------------------------------------------------------------
Funcia AfiseazaArbore realizeaz reprezentarea grafic a unei structuri de arbore binar rsturnat (rotit cu 90o n sensul acelor de ceasornic), conform urmtoarei specificaii:
1o Pe fiecare rnd se afieaz exact un nod; 2o Nodurile sunt ordonate de sus n jos n inordine;
-
3o Dac un nod se afieaz pe un rnd precedat de h blancuri, atunci fiii si (dac exist) se afieaz precedai de h-d blancuri. d este o variabil a crei valoare este stabilit de ctre programator i precizeaz distana dintre nivelurile arborelui; 4o Pentru rdcin, se alege o valoare corespunztoare a lui h, innd cont c arborele se dezvolt spre stnga.
Aceast modalitate de reprezentare grafic a arborilor binari este una dintre cele mai
simple i imediate, ea recomandndu-se n mod deosebit n aplicaiile didactice.
Trebuie subliniat faptul c simplitatea i transparena acestui program rezult din utilizarea recursivitii.
o Aceasta reprezint un argument n plus adus afirmaiei, c algoritmii
recursivi reprezint modalitatea cea mai potrivit de prelucrare a unor structuri de date care la rndul lor sunt definite recursiv.
o Acest lucru este demonstrat att de ctre funcia care construiete arborele
ct i de ctre procedura de afiare a acestuia, procedur care este un exemplu clasic de parcurgere n inordine a unui arbore binar.
o Avantajul utilizrii unui algoritm recursiv, devine i mai evident n
comparaie cu soluia nerecursiv a aceleiai probleme.
8. Arbori8.1. Arbori generalizai8.1.1. Definiii8.1.2. Tipul de date abstract arbore generalizat 8.1.3. Traversarea arborilor generalizai8.1.3.1. Traversarea arborilor generalizai prin tehnici bazate pe cutarea n adncime: preordine, inordine i postordine8.1.3.2. Traversarea arborilor generalizai prin tehnica cutrii prin cuprindere
8.1.4. Tehnici de implementare a TDA arbore generalizat8.2.4.1. Implementarea arborilor binari cu ajutorul structurii tablou 8.2.5.1. Traversarea arborilor binari prin tehnici bazate pe cutarea n adncime 8.2.5.2. Traversarea arborilor binari prin tehnica cutrii prin cuprindere