Arborele

Arborele

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

Realitatea complexa pe care o modelam ne arata insa legaturi intre 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 cateva 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 randul lor, se descompun in 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 incat sunt indeplinite conditiile:

exista un nod unic numit radacina arborelui;

celelalte noduri sunt repartizate in k>0 seturi disjuncte, fiecare set fiind la randul sau un arbore.

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

Terminologia folosita in descrierea arborilor este imprumutata din asemanarea structurii cu un arbore intors sau din paralelismul cu arborii genealogici.

Definim nivelul unui nod, recursiv, astfel:

Nivelul nodului radacina este 1;

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

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

1.  nodurile lui B sunt si noduri in A;

2.  arcele lui B sunt si arce in A;

3.  orice frunza din A care poate fi atinsa din radacina arborelui B trebuie sa apartina multimii nodurilor lui B.

Inaltimea unui arbore este maximum dintre nivelele nodurilor terminale sau echivalent 1+maximul dintre inaltimile subarborilor sai.

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

Arborele binar este arborele in care un nod are cel mult doi fii. In aceasta situatie se poate vorbi (pentru un arbore nevid) de cei doi subarbori (stang si drept) ai unui arbore. Schematic avem:

Arbore binar

Reprezentarea in memorie a arborilor poate fi statica sau dinamica. In cazul static arborii se pot simula cu ajutorul tablourilor.

Avantajul acestei implementari este urmatorul: fiecarui nod avand cel mult un tata, ii atasam in 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 campuri: un camp pentru memorarea informatiei specifice nodului (informatia utila) si doua campuri care contin adresa radacinii subarborelui stang, 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 in vizitarea fiecarui nod o singura data si prelucrarea informatiei continuta in el.

Doua tipuri de parcurgere a unui arbore sunt folosite frecvent: parcurgerea in latime si parcurgerea in inaltime.

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

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

Algoritm Parc_latime (radacina):

Initializeaza coada

Adauga radacina in coada

Cat timp coada nu este vida executa

Extrage element p din coada

Prelucreaza informatia utila din p

Daca p are fiu stang atunci

Adauga fiu stang in coada

Daca p are fiu drept atunci

Adauga fiu drept in coada

Sfarsit.

In cazul parcurgerii in adancime 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 in adancime este urmatoarea: 1, 2, 3, 4, 5, 7, 8, 9, 10, 6. Revenirea la fratele y dupa vizitarea descendentilor lui x poate fi realizata utilizand o stiva ajutatoare.

Pentru arborii binari, trei tipuri de parcurgere in adancime sunt uzuale: parcurgerea in preordine (RSD), in inordine (SRD) si in postordine (SDR). Prescurtarile au urmatoarea semnificatie:

• RSD - Radacina, Stanga, Dreapta - se prelucreaza radacina, subarborele stang, subarborele drept;
• SRD - Stanga, Radacina, Dreapta - se prelucreaza subarborele stang, radacina, subarborele drept;
• SDR - Stanga, Dreapta, Radacina - se prelucreaza subarborele stang, subarborele drept, radacina.

Pentru executia programelor care urmeaza aveti nevoie sa generati mai intai un arbore (optiune G). Introducerea de date se va face mai intai pentru subarborele stang, apoi pentru cel drept. Pentru a intelege mai bine, analizati figura de mai jos:

Arborele propriu-zis contine doar nodurile colorate. Zerourile 'legate' de arbore prin linii punctate doresc doar sa ilustreze locurile in 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 in cele doua programe va decurge astfel:

//ArbRec

# include 'stdio.h'

# include 'conio.h'

# include 'alloc.h'

const max_aloc=50;

struct pstruct

;

typedef struct pstruct PSTRUCT;

PSTRUCT *rad,*p;

int x,m;

char ch;

PSTRUCT *Gener_Arb()

else return NULL;

void RSD(PSTRUCT *p)

void SRD(PSTRUCT *p)

void SDR(PSTRUCT *p)

int NumarNod(PSTRUCT *p)

int Inaltime(PSTRUCT *p)

void main(void)

clrscr();

}

while (ch!='S');

TEMA

Pentru fixarea cunostintelor dobandite pana in prezent, inainte de a trece mai departe, este bine sa rezolvati aceste teme. Dupa rezolvarea lor puteti selecta o noua conversatie.

Intrebari de control

Probleme

Definiti: lista, stiva, coada, arborele.

Ce este o lista dublu inlantuita?

Listati functiile programului Static_Stiva

Listati functiile programului Dinamic_Coada

Listati functiile programului ArbRec

Sa se elaboreze programe / subprograme (Borland) C pentru:

1.  Calculul numarului de aparitii ale unui numar intreg a printre componentele unei liste implementate static;

2.  Calculul sumei termenilor de rang impar dintr-o lista simplu inlantuita;

3.  Calculul sumei termenilor mai mari strict decat un numar intreg a dintr-o lista dublu inlantuita;

4.  Calculul numarului de elemente pozitive dintr-o stiva (implementata static sau dinamic);

5.  Concatenarea (alipirea) a doua cozi implementate dinamic;

6.  Calculul sumei valorilor din nodurile unui arbore binar, cuprinse in intervalul [a,b].

Graful

Graful este se defineste ca fiind perechea G=(V,R),unde V este multimea nodurilor sau varfurilor, iar elementele multimii R se numesc muchii. Muchiile sunt perechi (v,w) din multimea VxV. Grafurile modeleaza relatii simetrice dintre obiecte simetrice dintre obiecte. Exemple de grafuri : harta cailor ferate dintr-o tara, harta care infatiseaza reteaua drumurilor cu doua sensuri de mers dintr-un oras, schema instalatiei de curent electric dintr-o institutie etc.

Un caz particular important al grafului este graful orientat sau digraful (notiunea de digraf vine de la directed graph). Digraful modeleaza relatii nesimetrice dintre obiecte.

De exemplu, se poate vorbi despre digraful datoriilor dintre membrii unui grup de persoane, despre digraful simpatiilor unui astfel de grup sau despre digraful care reprezinta o retea de comunicatii etc.. Matematic, un digraf se defineste ca fiind perechea G=(V,E), unde V este multimea nodurilor sau varfurilor, iar elementele multimii E se numesc arce. Arcele sunt perechi (v,w) din VxV : v se numeste baza arcului, iar w se numeste varful arcului. Se spune ca nodul w este nod adiacent lui v. Grafic , nodurile unui digraf se pot reprezenta prin cercuri sau patrate, iar arcurile prin sageti. Daca acestea sunt marcate cu numere sau nume , se spune ca sunt etichetate. Orice graf poate fi considerat digraf daca inlocuim o muchie (v,w) cu arcele (v,w) si (w,v).

O notiune importanta in legatura cu digrafurile este notiunea de drum sau cale. Un drum este o succesiune de varfuri v_1, v_2, v_3 .,v_k astfel incat exista arcele (v_1, v_2),

(v_2, v_3),.., (v_k-1, v_k). Daca un arc nu este etichetat , se considera ca este de lungime 1. Valoarea indicata de eticheta unui arc se numeste costul arcului. Un caz particular de drum este ciclul. Ciclul este un drum de la un varf la el insusi. Un digraf fara cicluri se numeste digraf aciclic.

Exista doua reprezentari frecvent utilizate pentru digrafuri :cu ajutorul matricii de adiacenta si cu ajutorul listelor de adiacenta.

Daca G=(V,E) este un digraf iar V= atunci matricea de adiacenta se defineste ca fiind matricea patrata A(nxn), astfel incat A[i,j]=1 daca exista arc de la nodul i la nodul j si A[i,j]=0 daca nu exista arc de la nodul i la nodul j. Avantajul reprezentarii unui digraf prin matrice de adiacenta permite accesul rapid la arcele grafurilor. In acelasi timp, aceasta reprezentare permite demonstrarea eleganta a unor importante teoreme din teoria grafurilor. Pe de alta parte, se poate constata cu usurinta faptul ca, in cazul unor grupuri de obiecte cu legaturi slabe intre ele , matricea de adiacenta este rara si deci mai putin recomandata pentru reprezentare.

O alternativa la reprezentarea prin matricea de adiacenta este lista de adiacenta. Intr-o lista de adiacenta toate nodurile i sunt indici intr-un vector x. In fiecare celula x[i] este memorata adresa unei liste care contine nodurile adiacente nodului x[i]. Implementarea listelor de adiacenta poate fi statica sau dinamica.