Structura de arbore. Arbori generalizati

1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se pot efectua asupra ei.

2. Aspecte teoretice.

2.1. Arbori si traversarea lor

Prin arbore se intelege o multime de n noduri de acelasi tip care, daca nu este vida, are un anumit nod numit radacina, iar restul nodurilor formeaza un numar finit de arbori, doi cate doi disjuncti.

Numarul fiilor unui nod formeaza gradul nodului. Gradul maxim al nodurilor unui arbore se numeste gradul arborelui. Adancimea unui nod este lungimea drumului unic de la radacina pana la acel nod.

Prin traversarea unui arbore se intelege executia unei anumite operatii asupra tuturor nodurilor arborelui. In timpul vizitarii nodurile sunt vizitate intr-o anumita ordine, astfel incat ele pot fi considerate ca si cum ar fi integrate intr-o lista liniara.

Exista trei moduri de ordonare (traversare) a unei structuri de arbore, numite preordine, inordine si postordine.

Cele trei moduri de traversare se definesc recursiv in felul urmator:

- daca arborele A este nul, atunci traversarea lui A in preordine, inordine si postordine se reduce la lista vida.

- daca A se reduce la un singur nod, atunci nodul insusi reprezinta traversarea in oricare din cele trei moduri.

- pentru restul cazurilor, fie arborele A cu radacina R si subarborii acestuia A₁, A₂,,A_k (figura 1.2). In acest caz:

1. Traversarea in preordine a arborelui A presupune traversarea radacinii R urmata de traversarea in preordine a lui A₁, apoi de traversarea in preordine a lui A₂, si asa mai departe pana la A_k inclusiv.

2. Traversarea in inordine presupune parcurgerea in inordine a subarborelui A₁, urmata de nodul radacina R si, in continuare, parcurgerea in inordine ale subarborilor A₂, A₃,, A_k.

3. Traversarea in postordine a arborelui A consta in traversarea in postordine a subarborilor A₁, A₂,, A_k si, in final, traversarea nodului radacina R.

De exemplu, pentru arborele reprezentat in figura 1.1, traversarea acestuia in cele trei moduri are ca rezultat urmatoarele:

preordine:      1, 2, 5, 6, 10, 11, 12, 3, 4, 7, 8, 9, 13, 14

inordine:         5, 2, 10, 6, 11, 12, 1, 3, 7, 4, 8, 13, 9, 14

postordine:     5, 10, 11, 12, 6, 2, 3, 7, 8, 13, 14, 9, 4, 1

2.2. Implementarea arborilor generalizati prin indicator spre parinte

O maniera simpla de implementare o reprezinta utilizarea unui tablou (A), in care fiecare intrare A[I] contine un indice la parintele nodului I. Deci, daca A[I].indice = J, atunci nodul J este parintele nodului I, exceptie facand cazul in care nodul I este chiar radacina arborelui.

Aceasta modalitate de implementare face uz de proprietatea arborilor ca orice nod are un singur parinte. Reprezentarea prin indicator spre parinte are insa dezavantajul implementarii dificile a operatiilor legate de fii. Pentru a facilita acest lucru, se impune stabilirea unei ordini artificiale a nodurilor in tablou, respectand urmatoarele reguli:

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

- numerotarea fiilor unui nod se face numai dupa ce nodul a fost numerotat; in consecinta, fiii vor avea intotdeauna un numar de ordine mai mare decit nodul parinte;

- numerele fiilor cresc de la stanga la dreapta.

In continuare, indicele parintelui este indicele nodului parinte in tabloul A, iar nodul radacina va avea ca parinte indicele -1. Pentru arborele din figura 1.1, in aceasta reprezentare, avem:

Indice: 0 1 2 3 4 5 6 7 8 9 10 11 12 13

Cheie: 1 2 5 6 10 11 12 3 4 7 8 9 13 14

Parinte: -1 0 1 1 3 3 3 0 0 8 8 8 11 11

Programul de mai jos creeaza un arbore implementat astfel si face o afisare a lui prin parcurgere in preordine. Dupa adaugarea unui nod, se creeaza si fiii lui, daca exista.

#include <stdio.h>

#include <conio.h>

#define nrMaxN 20

typedef struct _nodnod;

nod A[nrMaxN];

int nrEl; //numarul de elemente

void AdaugFii(int idxPar, int cheie, int niv)while(j);

void CreareAG()

void Afisare()

//parcurgere in preordine

void AfisareAG(int idx, int niv)

void main(void)

2.3. Implementarea arborilor generalizati cu structuri de adiacenta

Principial, fiecare nod trebuie sa contina, pe langa cheie si alte informatii specifice, adresele tuturor fiilor sai, asa cum este ilustrat in figura 1.3 (am considerat subarborele cu radacina 4 al arborelui din figura 1.1).

Intrucat numarul de fii variaza de la nod la nod, este bine sa construim pentru fiecare nod o lista inlantuita cu adresele fiilor lui, iar in nod sa memoram doar adresa de inceput a acestei liste.

In aceasta implementare se folosesc urmatoarele structuri de date:

struct _nodArb;

struct _listaPFii;

Schematic, un arbore implementat cu aceste structuri se poate reprezenta astfel (se considera ca exemplu subarborele cu radacina avand cheia 4 din arborele prezentat in figura 1.1):

2.3.1. Crearea arborilor. Insertia unui nod in arbore

Pentru inserarea unui nou nod in arbore, acesta trebuie intai creat, apoi inserat in arbore. Pe langa acestea, mai trebuie initializate campurile cu informatii specifice nodului.

Daca arborele este vid, noul nod va fi radacina lui. Daca nu este vid, pentru inserarea noului nod, adresa acestuia trebuie inserata in lista asociata nodului care-i va fi parinte. Presupunand ca dorim adaugarea noului nod la inceputul listei de pointeri spre fii, secventa de inserare va fi (p este noul nod din lista parintelui, nodNou este nodul de inserat, iar lf este inceputul listei parintelui):

p = new struct _listaPFii;

p->fiu = nodNou;

p->urm = lf;

lf = p;

2.3.2. Suprimarea unui nod

Daca eventualii fii ai nodului de sters trebuie mutati spre alte noduri, prima data se face acest lucru. Dupa ce am eliberat si lista de pointeri spre fii a nodului, putem sterge nodul. In afara de stergerea nodului propriu-zis, trebuie sters si nodul corespunzator din lista de fii a parintelui.

Daca se cere stergerea nodului impreuna cu toti descendentii sai, atunci putem folosi o functie recursiva ca si cea de mai jos.

void StergArb(struct nodArb *p)

//eventuale dezalocari pentru info din p

delete p;

}

2.3.3. Traversarea arborilor generalizati

Functiile de mai jos traverseaza un arbore generalizat in cele trei moduri.

void Preordine(struct _nodArb *p)

}

void Inordine(struct _nodArb *p)

}

}

void Postordine(struct _nodArb *p)

// prelucrare nod

}

3. Problema rezolvata

Sa se determine stramosul comun cel mai apropiat si sa se calculeze gradul de rudenie intre doua persoane, cunoscand toti ascendentii lor pe linia stramosului comun, cel putin pana la acesta. Gradul de rudenie se calculeaza prin insumare, pornind de la o persoana si mergand pe drumul cel mai scurt pana la cealalta numai pe legaturi parinte-fiu si stiind ca intre parinte si fiu gradul este 1.

Exemple: a. grad(frate1, frate2) grad(frate1, parinte) +

grad(parinte, frate2) = 1 + 1 = 2;

b. grad(bunic, nepot) = grad(bunic, tatal nepotului) + grad(tatal nepotului, nepot) =

1 + 1 = 2.

Rezolvare

Pentru determinarea gradului si a stramosului comun lansam o functie (DetNiv) care parcurge arborele in preordine. Pentru fiecare nod se numara cate din cele doua rude date se afla in subarborele sau. Stramosul comun va fi radacina celui mai mic subarbore care contine cele doua rude.

Observatie de implementare: Presupunem ca si cheie pentru noduri numele persoanelor, deci, pentru identificarea lor exacta se cere sa nu existe persoane cu acelasi nume in datele de intrare.

#include <stdio.h>

#include <conio.h>

#include <string.h>

typedef struct _listaPFiilistaPFii;

typedef struct _nodArbnodArb;

nodArb *rad;

char nume[100], nume1[100], nume2[100];

char s[100];

int nivel[3], i;

//adauga un nod in arbore

void AdgNod(nodArb **nod, int niv)

}while(nodNou != NULL);

}

else //nu am creat un nod

*nod = NULL;

//afisarea arborelui

void AfisArb(nodArb *p, int niv)

}

//stergerea arborelui

void StergArb(nodArb *p)

delete p->nume;

delete p; //stergem nodul

}

//determinarea nivelurilor celor 2 rude si al stramosului comun

int DetNiv(nodArb *p, int niv)

else

if(!nivel[2] && !strcmp(p->nume, nume2))

lf = p->lf //ne pozitionam pe inceputul listei de fii

while((!nivel[1] || !nivel[2]) && lf)

if(gasiti==2)

}

return gasiti;

void main(void)

else

getch();

}

}while(nume1[0]!='0');

StergArb(rad); //stergerea arborelui

4. Probleme propuse

4.1. Pentru cuprinsul unei carti memorat sub forma de arbore generalizat, in implementarea indicator spre parinte, sa se realizeze urmatoarele operatii interactive:

a) adaugarea unui capitol sau a unui subcapitol intr-un (sub)capitol dat.

b) stergerea unui (sub)capitol (cu toate subcapitolele lui).

c) mutarea unui subcapitol (cu toate subcapitolele lui) intr-un alt (sub)capitol dat.

4.2. Sa se scrie un program care creeaza un arbore generalizat cu noduri identificate prin chei. Pentru arborele construit, sa se determine urmatoarele:

a) pentru un anumit nod dat, afiseaza cheia tatalui, cheile fiilor, gradul si adancimea nodului.

b) gradul arborelui.

c) verifica daca doua noduri date sunt in relatia stramos-descendent.

d) realizeaza transformarea arborelui dat intr-un arbore simetric (in oglinda).

4.3. Se considera un arbore (in implementarea cu structuri de adiacenta) care reprezinta structura arborescenta a directoarelor si fisierelor de pe o partitie a unui disc (arborele este doar o simulare in memorie a structurii de directoare). Sa se realizeze mutarea continutului unui director din ierarhie intr-un alt director.

4.4. Se considera un arbore memorat sub forma "indicator spre parinte". Scrieti un program care identifica nodurile care sunt situate pe nivelurile impare (radacina se considera pe nivelul 0).