Aplicatii - Lucrarea nr.1

TDA ARBORE GENERALIZAT

5. Exercitii

5.1. Pentru arborele generalizat avand urmatoarea structura ( pentru fiecare nod intern e data lista fiilor ):

		a - b,c,d,e
		b - f,g
		d - h,i,j
		e - k
		j - l,m

se cere:

a) sa se reprezinte grafic
b) sa se specifice continutul SD pentru implementarea arborelui in toate cele patru variante
c) sa se traverseze arborele in toate cele trei modalitati
d) sa se gaseasca adancimea, lungimea drumului intern si gradul arborelui.

6. Probleme de implementare

6.1. Sa se implementeze TDA arbore generalizat in urmatoarele variante:

a) cu ajutorul tablourilor;
b) cu ajutorul listelor (pointerilor);
c) utilizand relatiile "primul-fiu" si "frate-drept".

Sa se discute comparativ performantele operatorilor implementati, inclusiv a traversarilor, in termenii functiei O.

6.2. Sa se scrie un program interactiv care realizeaza urmatoarele operatii intr-un arbore generalizat, fiecare nod fiind identificat printr-o cheie alfanumerica:

V - face arborele vid;
C - creaza arborele prin citirea cheilor si a fiilor nodurilor;
N - vizualizeaza structurat arborele pe niveluri;
T - afiseaza cheile nodurilor in cele trei parcurgeri;
P - afiseaza lungimea drumului intern;
R - verifica daca doua chei date sunt in relatia stramos-descendent;
I - cauta o cheie data, afisand urmatoarele informatii: - cheia tatalui; - cheile fiilor; - cheile fratilor; - adancimea nodului; - gradul nodului.

6.3. Sa se realizeze implementarea TDA Arbore Generalizat utilizand structura de date multilista. Sa se discute performantele operatorilor in termenii functiei O ( vezi Anexa 3 ).

7. Aplicatii

7.1. Sa se construiasca operatorul Grad_arbore(A) care returneaza gradul arborelui generalizat A, pentru implementarile din lucrare. Sa se discute comparativ performantele implementarilor realizate.

7.2. Sa se construiasca operatorul Suprima(N,A), care suprima nodul precizat N din arborele generalizat A, pentru oricare din variantele de implementare. Discutie asupra performantelor operatorului. ( Daca nodul nu e terminal, primul sau fiu i se suprapune, fiii acestuia devenind fratii celui care se suprima ).

7.3. Fiind dat un arbore generalizat, sa se implementeze operatorii Simetric(A,B) si Copia(A,C) care construiesc simetricul B (in oglinda), respectiv copia C ai arborelui original. Sa se afiseze cei trei arbori.