Arbori

Arbori

1. Arbori - notiuni introductive

Definitie: Un arbore este un graf conex si fara cicluri.

1.1 Proprietati

se considera G=( V , E ) un graf; urmatoarele afirmatii sunt echivalente

- G este arbore

- G este conex minimal cu n-1 muchii (daca se elimina o muchie nu mai este conex)

- G este aciclic maximal cu n-1 muchii (daca se adauga o muchie se formeaza un ciclu)

- orice pereche de noduri este legata de un lant si numai unul

2. varfurile unui arbore se numesc noduri

3. un arbore poate fi asezat cu nodurile pe nivele, pe primul nivel aflandu-se un varf numit radacina, iar pe celelalte nivele restul nodurilor

4. se numeste radacina a unui arbore un varf R V astfel incat x V , x r, exista unica lant de la r la x

5. se numeste subarbore graful ce porneste din fiecare varf al unui arbore

6. nodurile terminale ale unui arbore se numesc frunze

7. se umeste descendent direct / fiu/urmas al unui nod x intr-un arbore un varf y x si care se afla pe nivelul imediat urmator lui x (se numeste numai descendent al lui x un nod y care se afla pe unul din nivelele urmatoare celui pe care se afla x intre x si y exista un lant care pleaca din x )

8. se umeste ascendent direct / parinte/stramos al unui nod x intr-un arbore un varf y x si care se afla pe nivelul imediat anterior lui 616b19g x (se numeste numai ascendent al lui x un nod y care se afla pe unul din nivelele anterioare celui pe care se afla x intre x si y exista un lant care pleaca din x )

9. 2 noduri se numesc frati daca au acelasi parinte, se afla pe acelasi nivel si nu sunt adiacente

10. inaltimea unui arbore este maximul dintre nivelurile nodurilor terminale sau lungimea celui mai lung lant pornind de la radacina catre o frunza

11. se numeste ordinul nodului numarul de descendenti directi ai acestuia

12. daca G=(V,E) cu n 2 noduri, m muchii si p componente conexe,numarul v(G)=m-n+p se numeste numarul ciclomatic al grafului G

13. fie un graf G un subgraf partial al sau, care este arbore, se numeste arbore partial; graful G=(V,E) contine un arbore partial daca si numai daca G este conex

14. orice arbore cu mai mult de 2 noduri contine cel putin 2 noduri terminale

15. pentru n nivele, numarul maxim de noduri este 2 ⁿ-1

1.2. Metode de reprezentare

- matricea de adiacenta - ca la grafuri neorientate

- liste de adiacente

L1=

L2=

L4=

L5=

L7=

L8=

- vectori de tati

Observatii - varfurile care nu apar in vectorul de tati sunt frunze

- varfurile frati au acelasi tata

- se pot deduce drumurile care pleaca din radacina

- parcurgerea arborilor se face ca la grafuri neorientate

1.3. Aplictaii cu arbori

Arborele partial de cost minim (Algoritmul lui Kruscall)

Defunitie: se considera un graf G=(V,E) in care fiecare muchie are asociatao valoare pozitiva numita cost; se numeste costul grafului G suma costurilor muchiilor din componenta lui

- algoritmul lui Kruscall consta in determinarea unui arbore partial al unui graf cu cel mai mic cost posibil

- pasul 1: se ordoneaza muchiile in ordine crescatoare a costurilor

-pasul 2: se adauga la arborele partial primele 2 muchii din aceasta ordine

-pasul 3: cat timp numarul de muchii adaugate n-1 se cauta prima muchie disponibila din vectorul de muchii care nu formeaza ciclu cu muchiile deja alese

-pasul 4: se afiseaza cele n-1 muchii alese

Observatie: deoarece putem avea muchii cu acelasi cost, arborele partial de cost minim nu este unic

# include <iostream.h>

//numarul de varfuri si de muchii, costul total al arborelui

int n, m, ct, L[100];

// vectorul de muchii

struct muchii

e[100], h[100], aux;

void main ()

for (i=1;i<=m-1;i++)

for (j=i+1;j<=m;j++)

if (e[i].c>e[j].c)

h[1]=e[1];

h[2]=e[2];

ct=h[1].c+h[2].c;

k=2;

i=3;

while (k<=n-1)

else

if (L[j]==max)

L[j min;

}

}

cout<<"Arborele partial de cost minim este:"<<endl;

for (i=1;i<=n-1;i++)

cout<<"muchia "<<h[i].x<<h[i].y<<" cu costul "<<h[i].c<<endl;

}

1.3.2. Asezarea nodurilor unui arbore pe nivele

#include<iostream.h>

struct arbore *r;

arbore *creare (arbore *c)

return NULL;

void rsd (arbore *c)

//afiseaza nodurile de pe nivelul k

void nivel (arbore *c, int i, int k)

//determina nr de nivele

int nr_niv (arbore *c)

//afisare noduri

void afisare (arbore *c)

}

void main()

1.3.3. Aplicatii

# include <iostream.h>

int k1=0, k2=0, k3=0, k4=0, n=0, m=0, p=0, min=1000, max=0;

struct arbore *r;

arbore *creare (arbore *c)

//determina nr de noduri cu un sg descendent (k1) si cu doi (k2), numarul de noduri terminale (k3) si suma acestora (k4)

void rsd (arbore *c)

rsd (c->as);

rsd (c->ad);

}}

//nr de elemente negative, nule, pozitive

void sdr (arbore *c)

//min

void srd (arbore *c)

//inaltimea arborelui <numarul de nivele>

int h (arbore *c)

void main()

2. Arbori binari

Definitie: un arbore binar este o multime finita de noduri care este fie vida, fie reprezinta un arbore ordonat in care fiecare nod are cel mult doi descendenti.

- daca toate nodurile unui arbore, cu exceptia celor terminale au exact 2 descendenti, arborele se numeste arbore binar complet

- un arbore binar complet care are n noduri terminale, toate situate pe acelasi nivel, are in total 2n-1 noduri

2.1. Metode de reprezentare             

- vectori de descendenti (stanga, dreapta)

i V st[i]=

dr[i]=

i

st[i]

dr[i]

- vectori tata + descendent

i V T[i]=ascendentul lui i

D[i

i

T[i]

D[i]

- forma parantezata nodul respectiv paranteza deschisa descendent stang descendent drept paranteza inchisa 0 daca nu exista descendenti pt nodul respectiv

(00)))3(6(00)7(10(14(00)0)11(00))))

2.2. Parcurgerea arborilor binari

2.2.1. Parcurgerea in preordine RSD

# include <iostream.h>

struct arbore

*r;

arbore *creare (arbore *c)

void rsd (arbore *c)

void main ()

2.2.2. Parcurgerea in inordine SRD

# include <iostream.h>

struct arbore

*r;

arbore *creare (arbore *c)

void srd (arbore *c)

void main()

2.2.3. Parcurgerea in postordine           

SDR

#include<iostream.h>

struct arbore

*r;

arbore *creare (arbore *c)

void sdr (arbore *c)

void main()

2.3. Aplicatii cu arbori binari

2.3.1. Arbore binar de cautare/sortare

2.3.2. Forma poloneza a unei expresii aritmetice

expresie aritmetica poate fi transpusa intr-un arbore binar astfel:

- nodurile neterminale vor contine operatorii

- nodurile terminale vor contine operanzii

- operatorii vor fi introdusi in arbore in functie de ordinea lor de executie

E=

RSD: /*+ab+cd+*ef*gh

SDR: ab+cd+*ef*gh*+/

SRD: a+b*c+d/e*f+g*h