CATEGORII DOCUMENTE |
Liste
class elem
elem(char ch)
elem adaug(char ch)
void creare()
}
String direct(elem x)
String invers(elem x)
class Lista
unde operatorul are sensul 'diferit de'.
Sa presupunem ca la intrare apare: abc$c1 La iesire vom obtine:
abc
cba
Arbori
Numim arbore un graf neorientat conex si fara cicluri.
Aceasta nu este singurul mod in care putem defini arborii. Cateva definitii echivalente apar in urmatoarea teorema, expusa fara demonstratie.
Teorema. Fie G un graf cu n varfuri. Urmatoarele afirmatii sunt echivalente:
G este un arbore;
G are n-1 muchii si nu contine cicluri;
G are n-1 muchii si este conex;
oricare doua varfuri din G sunt unite printr-un unic drum;
G nu contine cicluri si adaugarea unei noi muchii produce un unic ciclu elementar;
G este conex, dar devine neconex prin stergerea oricarei muchii.
In foarte multe probleme referitoare la arbori este pus in evidenta un varf al sau, numit radacina. Alegerea unui varf drept radacina are doua consecinte:
Arborele poate fi asezat pe niveluri astfel:
radacina este asezata pe nivelul 0;
pe fiecare nivel i sunt plasate varfurile pentru care lungimea drumurilor care le leaga de radacina este i
se traseaza muchiile arborelui.
Aceasta asezare pe niveluri face mai intuitiva notiunea de arbore, cu precizarea ca in informatica 'arborii cresc in jos'.
Exemplul 3. Consideram urmatorul arbore si modul in care el este asezat pe niveluri prin alegerea varfului 5 drept radacina.
Arborele poate fi considerat un graf orientat, stabilind pe fiecare muchie sensul de la nivelul superior catre nivelul inferior.
Reprezentarea pe niveluri a arborilor face ca notiunile de fii (descendenti) ai unui varf, precum si de tata al unui varf sa aiba semnificatii evidente. Un varf fara descendenti se numeste frunza.
Un arbore binar este un arbore in care orice varf are cel mult doi descendenti, cu precizarea ca se face distinctie intre descendentul stang si cel drept. Din acesta definitie rezulta ca un arbore binar nu este propriu-zis un caz particular de arbore.
Primele probleme care se pun pentru arborii binari (ca si pentru arborii oarecare si pentru grafuri, asa cum vom vedea mai tarziu) sunt:
modul de reprezentare;
parcurgerea lor.
Forma standard de reprezentare a unui arbore binar consta in:
a preciza radacina rad a arborelui;
a preciza pentru fiecare varf i tripletul st(i) dr(i) si info(i), unde acestea sunt respectiv descendentul stang, descendentul drept si informatia atasata varfului.
Trebuie stabilita o conventie pentru lipsa unuia sau a ambilor descendenti, ca de exemplu specificarea lor prin simbolul l
Exemplul 4. Consideram de exemplu urmatorul arbore binar:
Presupunand ca informatia atasata fiecarui varf este chiar numarul sau de ordine, avem:
rad = 1
st = (2,3,4,l l l l l
dr = (8,5,l l l l l
info= (1,2,3,4,5,6,7,8,9)
Dintre diferitele alte reprezentari posibile, mai mentionam doar pe cea care se reduce la vectorul sau tata si la vectorul info. Pentru exemplul de mai sus:
tata=(l
Problema parcurgerii unui arbore binar consta in identificarea unei modalitati prin care, plecand din radacina si mergand pe muchii, sa ajungem in toate varfurile; in plus, atingerea fiecarui varf este pusa in evidenta o singura data: spunem ca vizitam varful respectiv. Actiunea intreprinsa la vizitarea unui varf depinde de problema concreta si poate fi de exemplu tiparirea informatiei atasate varfului.
Distingem trei modalitati standard de parcurgere a unui arbore binar:
Parcurgerea in preordine
Se parcurg recursiv in ordine: radacina, subarborele stang, subarborele drept.
Concret, se executa apelul preord(rad) pentru procedura:
procedure preord(x)
if x=l
then
else vizit(x); preord(st(x)); preord(dr(x))
end
Ilustram acest mod de parcurgere pentru exemplul de mai sus, figurand ingrosat radacinile subarborilor ce trebuie dezvoltati:
Parcurgerea in inordine
Se parcurg recursiv in ordine: subarborele stang, radacina, subarborele drept.
Ilustram acest mod de parcurgere pentru Exemplul 4:
Concret, se executa apelul inord(rad) pentru procedura:
procedure inord(x)
if x=l
then
else inord(st(x)); vizit(x); inord(dr(x))
end
Parcurgerea in postordine
Se parcurg recursiv in ordine; subarborele stang, subarborele drept, radacina.
Ilustram parcurgerea in postordine pentru Exemplul 4:
Concret, se executa apelul postord(rad) pentru procedura:
procedure postord(x)
if x=l
then
else postord(st(x)); postord(dr(x)); vizit(x)
end
Sortarea cu ansamble
Fie a=(a1,.,an) vectorul care trebuie sortat (ordonat crescator).
Metoda sortarii de ansamble va folosi o reprezentare implicita a unui vector ca arbore binar. Acest arbore este construit succesiv astfel:
radacina este 1;
pentru orice varf descendentii sai stang si drept sunt 2i si 2i+1 (cu conditia ca fiecare dintre aceste valori sa nu depaseasca pe n). Rezulta ca tatal oricarui varf i este tata(i)= i/2
Evident, fiecarui varf i ii vom atasa eticheta ai
Pentru 2k-1 n<2k arborele va avea k niveluri, dintre care numai ultimul poate fi incomplet (pe fiecare nivel i<k-1 se afla exact 2i varfuri).
Vectorul a se numeste ansamblu daca pentru orice i avem ai a2i si ai a2i+1 (daca fiii exista).
Sa presupunem ca subarborii de radacini 2i si 2i+1 sunt ansamble. Ne propunem sa transformam arborele de radacina i intr-un ansamblu. Ideea este de a retrograda valoarea ai pana ajunge intr-un varf ai carui descendenti au valorile mai mici decat ai. Acest lucru este realizat de procedura combin
procedure combin(i,n)
i 2i; b ai
while j n
if j<n & aj<aj+1 then j j+1
if b>aj
then a j/2 b; exit
else a j/2 aj; j 2j
a j/2 b
end
Timpul de executare pentru procedura combin este O(k)=O(log n)
Sortarea vectorului a se va face prin apelul succesiv al procedurilor creare si sortare prezentate mai jos.
Procedura creare transforma vectorul intr-un ansamblu; in particular in a1 se obtine cel mai mare element al vectorului.
Procedura sortare lucreaza astfel:
pune pe a1 pe pozitia n si reface ansamblul format din primele n-1 elemente;
pune pe a1 pe pozitia n-1 si reface ansamblul format din primele n-2 elemente;
etc.
procedure creare procedure sortare
for i= n/2 for i=n,2,-1
combin(i,n) a1 ai; combin(1,i-1)
end end
Timpul total de lucru este de ordinul O(n log n)
Asa cum am mentionat chiar de la inceput, structura de arbore este implicita si este menita doar sa clarifice modul de lucru al algoritmului: calculele se refera doar la componentele vectorului.
Arbori de sortare
Un arbore de sortare este un arbore binar in care pentru orice varf informatia atasata varfului este mai mare decat informatiile varfurilor din subarborele stang si mai mica decat informatiile varfurilor din subarborele drept.
Observatie. Parcurgerea in inordine a unui arbore de cautare produce informatiile atasate varfurilor in ordine crescatoare.
Fie a=(a1,an) un vector ce trebuie ordonat crescator. Conform observatiei de mai sus, este suficient sa cream un arbore de sortare in care informatiile varfului sa fie tocmai elementele vectorului. Pentru aceasta este suficient sa precizam modul in care prin adaugarea unei noi valori, sa obtinem tot un arbore de sortare.
Pentru exemplul considerat:
adaugarea valorii 6 trebuie sa conduca la crearea unui nou varf, cu informatia 6 si care este descendent stang al varfului cu informatia 7;
adaugarea valorii 16 trebuie sa conduca la crearea unui nou varf, cu informatia 16 si care este descendent drept al varfului cu informatia 15.
Presupunem ca un varf din arborele de sortare este o inregistrare sau obiect de tipul varf, ce contine campurile:
informatia info atasata varfului;
descendentul stang st si descendentul drept dr (lipsa acestora este marcata, ca de obicei, prin l
Crearea unui nou varf se face prin functia varf_nou care intoarce un nou varf:
function varf_nou(info)
creez un nou obiect/ o noua inregistrare x in care informatia este info, iar descendentul stang si cel drept sunt l
return x
end
Inserarea unei noi valori val (in arborele de radacina rad) se face prin apelul adaug(rad,val), unde functia adaug intoarce o inregistrare si are forma:
function adaug(x,val)
if x=l
then return varf_nou(val)
else if val<info(x)
then st(x) adaug(st(x),val)
else dr(x) adaug(dr(x),val)
end
Programul principal intreprinde urmatoarele actiuni:
citeste valorile ce trebuie ordonate si le insereaza in arbore;
parcurge in inordine arborele de sortare; vizitarea unui varf consta in tiparirea informatiei atasate.
Prezentam programul in Java:
class elem
elem(int ch)
elem adaug(elem x, int ch)
String parcurg(elem x)
class Arbsort
IO.writeln(Ob.parcurg(rad));
}
Arbori oarecare
Primele probleme care se pun sunt aceleasi ca pentru arborii binari: modalitatile de reprezentare si de parcurgere.
Exemplul 5. Consideram urmatorul arbore:
Se considera ca arborele este asezat pe niveluri si ca pentru fiecare varf exista o ordine intre descendentii sai.
Modul standard de reprezentare al unui arbore oarecare consta in a memora radacina, iar pentru fiecare varf i informatiile:
info(i) = informatia atasata varfului;
fiu(i) = primul varf dintre descendentii lui i
frate(i) = acel descendent al tatalui lui i, care urmeza imediat dupa i
Ca si pentru arborii binari, lipsa unei legaturi catre un varf este indicata prin l
Pentru arborele din Exemplul 5:
fiu =(2,5,7,8,10,11,l l l l l l
frate =(l l l l l l l
O alta modalitate de reprezentare consta in a memora pentru fiecare varf tatal sau. Aceasta modalitate este incomoda pentru parcurgerea arborilor, dar se dovedeste utila in alte situatii, care vor fi prezentate in continuare.
In unele cazuri este util sa memoram pentru fiecare varf atat fiul si fratele sau, cat si tatal sau.
Parcurgerea in preordine
Se parcurg recursiv in ordine radacina si apoi subarborii care au drept radacina descendentii sai.
Pentru Exemplul 5:
Concret, executam apelul Apreord(rad) pentru procedura:
procedure Apreord(x)
if x=l
then
else vizit(x); Apreord(fiu(x)); Apreord(frate(x))
end
Ca
aplicatie, sa presupunem ca informatiile atasate
varfurilor sunt functii de diferite aritati
(aritatea unei functii este numarul variabilelor de care depinde; o
functie de aritate 0 este o
Pentru Exemplul 5, vectorul de aritate este:
aritate=(3,2,1,2,1,3,0,0,0,0,0,0,0)
Aceasta forma se numeste forma poloneza directa.
Parcurgerea in postordine
Se parcurg recursiv in ordine subarborii radacinii si apoi radacina.
Pentru Exemplul 5:
Concret, executam apelul Apostord(rad) pentru procedura:
procedure Apostord(x)
if x=l
then
else y fiu(x);
while y<>l
Apostord(y); y frate(x)
vizit(x)
end
Pentru aplicatia anterioara, dorim sa calculam valoarea expresiei functionale, cunoscand valorile frunzelor. Evident, trebuie sa parcurgem arborele in postordine.
class varf
varf(int val)
void creare()
void creare(varf x)
IO.write('fratele lui ' + x.v + ' : '); d = IO.read();
if( !Double.isNaN(d) )
}
String pre(varf x)
void post(varf x)
IO.write(x.v + ' ');
}
}
class Arbori
}
Parcurgerea pe niveluri
Se parcurg varfurile in ordinea distantei lor fata de radacina, tinand cont de ordinea in care apar descendentii fiecarui varf. Pentru Exemplul 5:
Pentru implementare vom folosi o coada C, in care initial apare numai radacina. Atata timp cat coada este nevida, vom extrage primul element, il vom vizita si vom introduce in coada descendentii sai:
C ; C rad
while C
x C; vizit(x);
y fiu(x);
while y l
y T C; y frate(x)
end
Parcurgerea pe niveluri este in general utila atunci cand se cauta varful care este cel mai apropiat de radacina si care are o anumita proprietate/informatie.
Pentru a include in programul anterior si parcurgerea pe niveluri, putem proceda astfel:
in metoda main adaugam instructiunea:
IO.writeln('rNiveluri : ' +'t' + Ob.niveluri() );
in clasa varf adaugam clasa interna elem si metoda niveluri
class elem
}
String niveluri()
}
return s;
}
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1879
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved