Arborele

Listele reprezinta mijloace simple si practice de a reprezenta organizarea liniara a obiectelor.

Realitatea complexa pe care o modelam ne arata însa legaturi între obiecte care depasesc modelul liniar. Grafurile, digrafurile si ca un caz particular al acestora - arborii - reprezinta structuri capabile sa surprinda complexitatea legaturilor dintre obiecte.

Arborele

Cu ajutorul arborilor se pot descrie foarte fidel structurile de tip ierarhic (piramidal). Iata câteva exemple: structura de conducere a unei firme, organizarea administrativ teritoriala dintr-o tara, organizarea unei armate, structura unei carti, descrierea unui obiect ca o reuniune de obiecte componente care, la rândul lor, se descompun în obiecte s.a.m.d.

Ultimul exemplu reliefeaza cel mai bine caracterul recursiv al structurii arborescente. Definim recursiv un arbore ca un set finit de unul sau mai multe noduri, astfel încât sunt îndeplinite conditiile:

exista un nod unic numit radacina arborelui;
celelalte noduri sunt repartizate în k>0 seturi disjuncte, fiecare set fiind la rândul sau un arbore.

Grafic, putem reprezenta un arbore ca o multime de noduri sau vârfuri (fiecare obiect are asociat un nod) legate între ele prin arce care reflecta natura relatiei dintre obiecte.

Observatii:

In orice nod intra cel mult un arc;
In nodul radacina nu intra nici un arc;
Nodurile pot fi etichetate sau nu.

Terminologia folosita în descrierea arborilor este împrumutata din asemanarea structurii cu un arbore întors sau din paralelismul cu arborii genealogici.

Remarci:

nodul 1 este "radacina" si în acelasi timp "tata" pentru nodurile"fii" 2,5,6 care sunt între ele "frati";
nodurile 9 si 10 sunt "descendenti" ai nodului "stramos" 5;
nodurile fara nici un fiu se numesc noduri terminale sau "frunze" (exemple: 3,4,9,10,6).

Observatie:

Termenii tata, fiu, frate oglindesc relatii directe între noduri, iar termenii stramos, descendent - relatii indirecte.

Definim nivelul unui nod, recursiv, astfel:

Nivelul nodului radacina este 1;
Nivelul oricarui nod diferit de nodul radacina este nivelul tatalui sau +1.

Observatie. Nivelul unui nod este 1+numarul de arce care alcatuiesc un "drum" de la nodul "radacina" la el. Exemplu: nodurile 3,4,7 au nivelul 3, nodurile 9 si 10 au nivelul 5.

Un subarbore B pentru arborele A este orice arbore care îndeplineste conditiile:

nodurile lui B sunt si noduri în A;
arcele lui B sunt si arce în A;
orice frunza din A care poate fi atinsa din radacina arborelui B trebuie sa apartina multimii nodurilor lui B.

Observatie. Conditia 3 este esentiala; mai jos prezentam un exemplu de arbore care, desi îndeplineste primele doua conditii, nu este totusi subarbore.

Înaltimea unui arbore este maximum dintre nivelele nodurilor terminale sau echivalent 1+maximul dintre înaltimile subarborilor sai.

Exemplu:

Arborele prezentat în figura de mai sus are înaltimea 5.

Un tip de arbore special, cu aplicatii interesante în tehnicile de programare este arborele binar.

Arborele binar este arborele în care un nod are cel mult doi fii. În aceasta situatie se poate vorbi (pentru un arbore nevid) de cei doi subarbori (stâng si drept) ai unui arbore. Schematic avem:

Arbore binar

Reprezentarea în memorie a arborilor poate fi statica sau dinamica. În cazul static arborii se pot simula cu ajutorul tablourilor.

Exemplu: În tabloul arbore cu n componente, arbore(i) (i=1...n) reprezinta tatal nodului i. Astfel, arborele din figura de mai sus se poate reprezenta sub forma:

Avantajul acestei implementari este urmatorul: fiecarui nod având cel mult un tata, îi atasam în tablou o singura informatie (Luam arbore(i)=0 daca nodul i este radacina).

Datorita dinamismului structurilor modelate printr-un arbore, varianta de implementare dinamica este preferabila variantei statice. In acest caz, daca arborele este binar, o celula va contine trei câmpuri: un câmp pentru memorarea informatiei specifice nodului (informatia utila) si doua câmpuri care contin adresa radacinii subarborelui stâng, respectiv drept.

Operatiile fundamentale asupra arborilor includ: parcurgerea arborelui, stergerea, cautarea sau adaugarea unui nod.

Vom prezenta operatia de parcurgere a unui arbore, care consta în vizitarea fiecarui nod o singura data si prelucrarea informatiei continuta în el.

Doua tipuri de parcurgere a unui arbore sunt folosite frecvent: parcurgerea în latime si parcurgerea în înaltime.

In cazul parcugerii în latime se viziteaza si prelucreaza nodurile în ordinea: radacina, nodurile de la stânga spre dreapta de pe primul nivel, de pe al doilea nivel etc. Astfel, rezultatul parcurgerii în latime a arborelui din figura 12.18 este lista de noduri 1, 2, 5, 6, 3, 4, 7, 8, 9, 10.

Putem realiza pacurgerea în latime a unui arbore binar printr-un algoritm care utilizeaza o coada drept element ajutator:

Algoritm Parc_latime (radacina):

Initializeaza coada
Adauga radacina în coada
Cât timp coada nu este vida executa
...Extrage element p din coada
...Prelucreaza informatia utila din p
...Daca p are fiu stâng atunci
......Adauga fiu stâng în coada
...Daca p are fiu drept atunci
......Adauga fiu drept în coada
Sfârsit.

Observatie. Practic la fiecare pas al iteratiei se extrage un element din coada, se prelucreaza, apoi se adauga - daca exista - fiii sai.

In cazul parcurgerii în adâncime trecerea de la un nod x la fratele sau y din dreapta se face numai dupa ce s-au vizitat si prelucrat toate nodurile descendente din x. Liniarizarea arborelui din figura 12.18 prin parcurgerea în adâncime este urmatoarea: 1, 2, 3, 4, 5, 7, 8, 9, 10, 6. Revenirea la fratele y dupa vizitarea descendentilor lui x poate fi realizata utilizând o stiva ajutatoare.

Pentru arborii binari, trei tipuri de parcurgere în adâncime sunt uzuale: parcurgerea în preordine (RSD), în inordine (SRD) si în postordine (SDR). Prescurtarile au urmatoarea semnificatie:

RSD - Radacina, Stânga, Dreapta - se prelucreaza radacina, subarborele stâng, subarborele drept;
SRD - Stânga, Radacina, Dreapta - se prelucreaza subarborele stâng, radacina, subarborele drept;
SDR - Stânga, Dreapta, Radacina - se prelucreaza subarborele stâng, subarborele drept, radacina.

Pentru executia programelor care urmeaza aveti nevoie sa generati mai întâi un arbore (optiune G). Introducerea de date se va face mai întâi pentru subarborele stâng, apoi pentru cel drept. Pentru a întelege mai bine, analzati figura de mai jos:

Arborele propriu-zis contine doar nodurile colorate. Zerourile "legate" de arbore prin linii punctate doresc doar sa ilustreze locurile în care trebuie intordus terminatorul de ramura (0 pentru programele date).

Urmatorul esantion desprins din executia programului este comun pentru ambele variante (recursiv, nerecursiv) si va ajuta sa intelegeti modul in care se genereaza arborele (care va fi ulterior parcurs prin cele 3 metode).

Pentru arborele din figura, procedura de generare a arborelui în cele doua programe va decurge astfel:

G: Generare Arbore Binar
1. Parcurgere in preordine (RSD)
2. Parcurgere in inordine (SRD)
3. Parcurgere in postordine (SDR)
4. Numar noduri arbore
5. Inaltime arbore
S. Sfarsit program
Optiunea dvs. va rog: g
x=100
x=20
x=0
x=10
x=0
x=0
x=30
x=40
x=0
x=50
x=0
x=0
x=0
0

G: Generare Arbore Binar
1. Parcurgere in preordine (RSD)
2. Parcurgere in inordine (SRD)
3. Parcurgere in postordine (SDR)
4. Numar noduri arbore
5. Inaltime arbore
S. Sfarsit program
Optiunea dvs. va rog: ...

Nota. Programul ArbRec ilustreaza cele trei moduri de parcurgere prezentate (procedurile RSD, SRD, SDR) precum si generarea unui arbore (procedura Gener_Arb), aflarea înaltimii unui arbore (procedura Inaltime) si aflarea numarului de noduri dintr-un arbore (procedura NumarNod).

Program ArbRec;
type
...pstruct=^struct;
...struct=record
...util:integer;
...st,dr:pstruct
end;
var
...rad,p:pstruct;
...ch:char;
...x,m:integer;

procedure Gener_Arb(var p:pstruct);
begin
...write('x=');readln(x);
...if x<>0 then
...begin
......new(p);
......p^.util:=x;
......Gener_Arb(p^.st);
......Gener_Arb(p^.dr)
...end
...else
......p:=nil
end;

procedure RSD(p:pstruct);
{preordine}
begin
...if p<>nil then
...begin
......write(p^.util:2);
......RSD(p^.st);
......RSD(p^.dr)
...end
end;

procedure SRD(p:pstruct);
{inordine}
begin
...if p<>nil then
...begin
......SRD(p^.st);
......write(p^.util:2);
......SRD(p^.dr)
...end
end;

procedure SDR(p:pstruct);
{postordine}
begin
...if p<>nil then
...begin
......SDR(p^.st);
......SDR(p^.dr);
......write(p^.util:2)
...end
end;

function NumarNod(p:pstruct):byte;
begin
...if p=nil then
......NumarNod:=0
...else
......NumarNod:=1+NumarNod(p^.st)+NumarNod(p^.dr)
end;

function Inaltime(p:pstruct):byte;
var
...ist,idr:byte;
begin
...if p=nil then
......Inaltime:=0
...else
...begin
......ist:=Inaltime(p^.st);
......idr:=Inaltime(p^.dr);
......if ist > idr then
.........Inaltime:=ist+1
......else
.........Inaltime:=idr+1
...end
end;

begin {program principal}
...repeat
......writeln('G.Generare arbore binar');
......writeln('1.Parcurgere in preordine (RSD)');
......writeln('2.Parcurgere in inordine (SRD)');
......writeln('3.Parcurgere in postordine(SDR)');
......writeln('4.Numar noduri arbore');
......writeln('5.Inaltime arbore');
......writeln('S.Sfirsit program');
......write('Optiunea dvs. va rog:');readln(ch);
...case upcase(ch) of
......'G':Gener_Arb(rad);
......'1':RSD(rad);
......'2':SRD(rad);
......'3':SDR(rad);
......'4':begin
.........m:=NumarNod(rad); writeln('Arborele are ',m,' noduri')
.........end;
......'5':begin
.........m:=Inaltime(rad); writeln('Arborele are inaltimea ',m)
.........end
......end;
......readln
...until ch in ['s','S']
end {ArbRec}.

Observatii:

Toate procedurile sunt recursive, deci stiva este prezenta în mod implicit;
Procedura de generare creeaza arborele în ordinea RSD; legaturile Nil ale nodurilor terminale sunt semnalate tastând cifra 0 (în locul cifrei zero se poate folosi orice alt marcator);
Datorita existentei implicite a stivei, procedurile sunt simple si elegante.

Nota. Programul ArbNeRec ilustreaza folosirea cozii si a stivei în mod explicit pentru implementarea operatiunilor de parcurgere în latime (procedura ParcLatime), parcurgere RSD si SRD (procedurile RSDstiva, respectiv SRDstiva). Operatiile de initializare,adaugare si extragere pentru stiva si coada sunt cele prezentate la paragrafele Stiva si Coada si sunt grupate aici în unitatea coadasti. Procedura SDRstiva (folosind explicit stiva) este lasata drept exercitiu cititorului.

Program ArbNeRec;
uses coadasti;
procedure RSDstiva(p:pstruct);
begin
...InitStiva;
...while (p <> nil) or not StivaVida do
...begin
......while p <> nil do
......begin
.........write(p^.util:3);
.........if p^.dr <> nil then
............AdaugaEls(p^.dr,cod);
............p:=p^.st
......end;
......ExtragEls(p,cod)
...end
end;

procedure SRDstiva(p:pstruct);
begin
...InitStiva;
...while (p <> nil) or not StivaVida do
...begin
......while p <> nil do
......begin
.........AdaugaEls(p,cod);
.........p:=p^.st
......end;
......if not StivaVida then
......begin
.........ExtragEls(p,cod);
.........write(p^.util:3);
.........p:=p^.dr
......end
...end
end;

procedure ParcLatime(p:pstruct);
begin
...InitCoada;
...AdaugaEl(p,cod);
...while not CoadaVida do
...begin
......ExtragEl(p,cod);
......write(p^.util:3);
......if p^.st <>nil then
.........AdaugaEl(p^.st,cod);
......if p^.dr <> nil then
.........AdaugaEl(p^.dr,cod)
...end
end;

begin {program principal}
...repeat
......writeln('G.Generare arbore binar');
......writeln('R.Parcurgere in preordine (RSD)');
......writeln('L.Parcurgere in latime');
......writeln('S.Parcurgere in postordine(SRD)');
......writeln('E.Sfirsit program');
......write('Optiunea dvs. va rog:');readln(ch);
......case upcase(ch) of
.........'G':Gener_Arb(rad);
.........'R':RSDstiva(rad);
.........'L':ParcLatime(rad);
.........'S':SRDstiva(rad)
......end;
......readln
...until ch in ['e','E']
end {ArbNeRec}.

Sursa (Borland) PASCAL a unitatii coadasti este listata în continuare.

UNIT coadasti;
INTERFACE
type
...pstruct=^struct;
...struct=record
...util:integer;
...st,dr:pstruct
end;
const
...max_aloc=50;
var
...stiva,coada:array[1..max_aloc] of pstruct;
...n,m,virf,pcap,pcoada:byte;
...cod:boolean;
...rad,p:pstruct;
...ch:char;
function StivaVida:boolean;
function CoadaVida:boolean;
procedure Gener_Arb(var p:pstruct);
procedure InitStiva;
procedure AdaugaEls(p:pstruct;var cod:boolean);
procedure ExtragEls(var p:pstruct;var cod:boolean);
procedure InitCoada;
procedure AdaugaEl(p:pstruct;var cod:boolean);
procedure ExtragEl(var p:pstruct;var cod:boolean);

IMPLEMENTATION

function StivaVida:boolean;
begin
...StivaVida:=virf=1
end;

procedure Gener_Arb(var p:pstruct);
var
...x:byte;
begin
...write('x=');readln(x);
...if x<>0 then
...begin
......new(p);
......p^.util:=x;
......Gener_Arb(p^.st);
......Gener_Arb(p^.dr)
...end
...else
......p:=nil
end;
procedure InitStiva;
begin
...virf:=1
end;

procedure AdaugaEls(p:pstruct;var cod:boolean);
begin
...if virf>max_aloc then
......cod:=false
...else
...begin
......stiva[virf]:=p;
......virf:=virf+1;
......cod:=true
...end
end;

procedure ExtragEls(var p:pstruct;var cod:boolean);
begin
...if virf=1 then
......cod:=false
...else
...begin
......virf:=virf-1;
......p:=stiva[virf];
......cod:=true
...end
end;

function CoadaVida:boolean;
begin
...CoadaVida:=n=0
end;
procedure InitCoada;
begin
...pcap:=1;
...pcoada:=1;
...n:=0
end;

procedure AdaugaEl(p:pstruct;var cod:boolean);
begin
...if n>=max_aloc then
......cod:=false
...else
...begin
......coada[pcoada]:=p;
......pcoada:=(pcoada+1) mod max_aloc;
......if pcoada=0 then
.........pcoada:=max_aloc;
.........n:=n+1;
.........cod:=true
......end
end;
procedure ExtragEl(var p:pstruct;var cod:boolean);
begin
...if n=0 then
......cod:=false
...else
...begin
......p:=coada[pcap];
......pcap:=(pcap+1) mod max_aloc;
......if pcap=0 then
.........pcap:=max_aloc;
......n:=n-1;
......cod:=true
...end
end;
end {coadasti}.

Observatie. In scopul prezentarii unor proceduri usor de urmarit, în programul ArbNerec s-au omis instructiunile de test asupra valorii parametrului de eroare cod (s-a facut ipoteza ca spatiul de memorie destinat stivei si cozii folosite este suficient de mare pentru arborii prelucrati).