Structuri de Date

L A B O R A T O R 12b

Arbori 2-4

Intr-un arbore 2-4 fiecare nod contine M valori si M+1 pointeri catre nodurile fii. (M intre 1 si 3). In fiecare nod valorile sunt ordonate crescator. Exemplu de arbore 2-4 :

30 , 50 , 70 / | \ \

10,20,25 35,40,45 60 80

1. Structura unui nod de arbore 2-4 cu valori intregi este definita astfel:

#define M 3 // nr maxim de valori pe nodtypedef struct bnod { int n; // numar de valori dintr-un nod int val[M]; // valori din nod struct bnod* leg[M+1]; // legaturi la noduri fii} bnod;

Valorile din subarborele cu radacina leg[i] sunt mai mici decat val[i] iar valorile din subarborele cu radacina leg[i+1] sunt mai mari decat val[i].

Sa se scrie functiile:

bnod* make (int n,int v[],bnod* lnk[]); // creare nod cu date din v si lnk void write (bnod* p); // afisare adresa si continut nod p (pointeri si valori)

Legaturile nefolosite dintr-un nod se vor face zero.

Functie "build" construieste arborele 2-4 dat ca exemplu:

bnod* build () { int rad[]={30,50,70}, unu[]={10,20,25},doi[]={35,40,45}, trei[]={60},patru[]={80}; bnod* a[4]={0,0,0,0}; // legaturi nod frunza bnod* t1=make (3,unu,a); bnod* t2=make(3,doi,a); bnod* t3=make(1,trei,a); bnod* t4=make(1,patru,a); a[0]=t1; a[1]=t2; a[2]=t3; a[3]=t4; return make (3,rad,a);// nod radacina}

Pentru verificare se adauga apelul functiei "write" in functia "make"astfel ca sa se afiseze fiecare nod creat (pe o linie separata).

2. Sa se scrie o functie pentru afisarea valorilor dintr-un arbore 2-4 in ordine crescatoare (pe o singura linie), prin vizitare infixata:

void infix (bnod* r);

Sa se verifice functia infix prin afisarea valorilor din arborele creat.

3. Sa se scrie o functie pentru afisarea structurii unui arbore 2-4 prinvizitare prefixata, cu indentare diferita la fiecare nivel (valorile dintr-un nodpe o aceeasi linie, separate prin virgule):

void prefix ( bnod* r, int ns); // ns=numar de spatii

Exemplu de afisare pentru arborele anterior:

30,50,70, 10,20,25, 35,40,45, 60, 80,

4. Sa se scrie o functie "split" care sparge un nod plin si creeaza unnod nou: void split (bnod* p, int & med, bnod* & nou);

"med" este valoarea mediana (din pozitia M/2) din nodul p, care se duce sus

Algoritm: - Se modifica numarul de valori din p (raman m=M/2 valori) - Se muta ultimele m valori din p intr-un vector a - Se muta ultimele m adrese din p intr-un vector b - Se creeaza nodul "nou' cu M-m-1 valori luate din vectorul a si cu legaturile luate din vectorul b (folosind functia "make")

Pentru verificare se va aplica functia "split" pe nodul radacina si sevor afisa arborii cu radacinile "p" si "nou" si valoarea "med". Se va crea apoi un nod cu valoarea "med" si cu fii p si nou, care vafi noua radacina a arborelui; se va afisa (prefixat) acest arbore.

5. Sa se scrie o functie care introduce o valoare x si legatura "legx"in nodul cu adresa p (nu se mai verifica daca este loc in nodul p):

void ins (int x, bnod* legx, bnod* p); // legx=0 daca p este frunza

Algoritm: - Se mareste numarul de valori din p (p->n) - Se determina pozitia i unde trebuie introdus x in vectorul de valori din nodul p ( 0 n) - Se deplaseaza la dreapta in vectorii p->val si p->leg pentru a elibera pozitia i - Se introduc x si legx in pozitia i din cei doi vectori

Pentru verificare se vor adauga succesiv valorile 10,90,12,53,28,32 si seva afisa arborele (infixat si prefixat) dupa fiecare adaugare.

6. Functiilea urmatoare adauga o valoare x intr-un arbore cu radacinar si sparge nodurile pline de pe calea de la radacina la nodul frunza careva contine pe x:

void findsplit (int x, bnod* & r, bnod* & pp) { // pp=parinte nod r bnod* p=r; bnod* nou, *rnou; int med; // val mediana dintr-un nod plin if (p->n==M) { // daca nod plin split(p,med,nou); // sparge nod cu creare nod nou if (pp!=0) // daca nu e nodul radacina ins(med,nou,pp); // pune med in nodul parinte else { // daca p e nodul radacina rnou= new bnod; // noua radacina rnou->val[0]=med; // med trece in noua radacina rnou->leg[0]=r; rnou->leg[1]=nou; // la stanga r, la dreapta nou rnou->n=1; r=rnou; pp=rnou; // modifica radacina si parinte nod curent } if (x > med) p=nou; // else p=p ( continua cautarea din p) } // cauta subarborele i al lui p care va contine pe x int i=0; while (in && x > p->val[i]) i++; if (x==p->val[i]) return ; // daca x exista in p nu se mai adauga if (p->leg[0]==0 ) // daca p e nod frunza ins (x,0,p); // atunci se introduce x in p else { pp=p; p=p->leg[i]; // cauta in fiul i al lui p findsplit(x,p,pp); // apel recursiv } } // adauga x la arborele cu radacina rvoid add (int x, bnod* & r) { bnod* pp=0; findsplit(x,r,pp);}

Sa se verifice prin adaugarea succesiva a urmatoarelor valori la arborelecreat anterior: 6,8,42,83,84,86,92,90,91,93 La fiecare pas se afiseaza valoarea adaugata si arborele (prefixat si infixat).

7. Sa se scrie o functie pentru determinarea numarului de noduri dintr-unarbore B cu radacina r: int size (bnod* r); Sa se adauge apelul functiei "size" in ciclul de adaugare valori din programulanterior.

8. Sa se scrie o functie care cauta nodul ce contine o valoare data x sau nodul frunza care va contine valoarea cautata dar negasita:

bnod* find (bnod* r, int x, bnod* & pp);

Rezultatul functiei este adresa nodului care va contine x sau NULL dacax exista in arbore; "pp" este adresa nodului parinte al nodului gasit. Cautarea se opreste la un nod frunza (care are leg[0]==0) sau la un nodcare contine pe x. Sa se verifice prin afisarea primei valori din nodurile gasit de "find"si "pp". Se vor cauta valorile 21, 33, 41, 65.