Aplicatii - Lucrarea nr.2

TDA ARBORE BINAR

5. Exercitii

5.1. Pentru un ABO initial vid, se cere:

a) Sa se specifice configuratia dupa insertia cheilor: 40,55,21,50,42,56,10,30,26,1,11,90,75,200 ;

b) respectiv dupa suprimarea fiecareia din cheile: 40,90,30,26,21,55,50,42;

c) Pentru subarborele obtinut dupa ultima stergere de la b), scrieti succesiunea cheilor pentru parcurgerea in preordine, inordine si postordine.

5.2. Pentru arborele generalizat de la exercitiul 5.1. de la Lucrarea 1, sa se gaseasca arborele binar echivalent si sa se scrie succesiunile de chei obtinute pentru parcurgerile in inordine si preordine.

5.3. Demonstrati prin inductie ca numarul nodurilor cu doi descendenti dintr-un ABO este cu unu mai mic decat cel al frunzelor.

6. Probleme de implementare

6.1. Se cere sa se implementeze TDA Arbore Binar Ordonat in urmatoarele variante: a) utilizand structura de date tablou; b) cu ajutorul pointerilor. Sa se discute comparativ performantele operatorilor implementati.

6.2. Sa se realizeze o clasa TArboreABO cu urmatorii operatori:

• Adauga(cheie); Sterge(cheie) - insereaza, respectiv suprima nodul cu cheia data
• Prezent(cheie); - verifica daca exista un nod cu cheia data
• Inordine, Preordine, Postordine - afiseaza nodurile conform cu ordinea de parcurgere
• Inaltime - calculeaza inaltimea (numarul de nivele) a arborelui
• TiparArbore- permite vizualizarea pe nivele a arborelui ( rotit cu 90 grade spre dreapta ). (O rezolvare a acestei probleme este data in Anexa 4)

7. Aplicatii

7.1.

I. Se cere sa se construiasca o lista simplu inlantuita, ale carei noduri au chei de tip sir de caractere. Cheile se introduc in lista prin citire de la tastatura sau dintr-un fisier, intr-o ordine aleatoare. Pot exista chei multiple.

II. Pornind de la aceasta lista, se cere sa se construiasca un arbore binar ordonat cu toate cheile din lista, fiecareia asociindu-i-se si contorul aparitiilor sale in lista initiala. Se va utiliza implementarea bazata pe pointeri.

III. Se cere sa se implementeze in maniera interactiva urmatoarele operatii:

1. vizualizarea structurata a continutului nodurilor arborelui construit pe niveluri;
2. pentru doua chei precizate sa se stabileasca: -daca sunt in relatia stramos-descendent sau -daca sunt situate pe acelasi nivel, caz in care se afiseaza numarul nivelului respectiv;
3. determinarea si afisarea adancimii arborelui;
4. sa se suprime: - nodul cu cheia minima; - toate nodurile cu contorul mai mic decat o valoare data; - nodul cu o cheie data; - tatal nodului cu cheia data; - fiul drept al nodului cu cheia data.
5. pentru o cheie data sa se tipareasca toti descendentii nodului care o contine (subarborele a carui radacina este nodul cu cheia precizata);
6. pentru o cheie precizata sa se afiseze cheile nodurilor parinte, frate drept, frate stang, fiu drept, fiu stang.

7.2. Sa se construiasca arborele binar ordonat perfect echilibrat, avand aceleasi chei ca si ABO construit la 7.1. Sa se vizualizeze cei doi arbori si sa li se compare inaltimile.

7.3. Se cere sa se construiasca un arbore generalizat (in una din implementarile precizate in Lucrarea 1 avand drept chei siruri de caractere. Pornind de la acest acest arbore:

1. sa se transforme in arborele binar echivalent;
2. sa se vizualizeze arborii si sa li se compare inaltimile;
3. sa se afiseze cheile ambilor arbori la parcurgerea in inordine si preordine (parcurgerile in preordine trebuie sa conduca la aceleasi secvente de chei ).

7.4. Sa se redacteze operatorii care creaza copia si simetricul in oglinda ai unui arbore binar dat. Sa se vizualizeze cei trei arbori.

7.5. Sa se realizeze un program care pornind de la o expresie aritmetica in format infix care contine operanzi (identificatori de o singura litera), operatorii +, -,*, / si paranteze, construieste arborele de parcurgere asociat. Expresia aritmetica se introduce de la tastatura. Se vizualizeaza arborele de parcurgere obtinut. Se introduc interactiv valori pentru toti identificatorii si se evalueaza expresia pornind de la forma postfix a expresiei rezultata din parcurgerea in postordine a arborelui de parcurgere.

7.6. Sa se implementeze operatorul care testeaza daca daca doi arbori binari au aceeasi forma geometrica.

Indicatii

Fie A1=(S1,R,D1) si A2=(S2,R,D2) cei doi arbori. A1 si A2 au aceeasi forma geometrica daca S1 are aceeasi forma cu S2 si D1 are aceeasi forma cu D2.

7.7. Pornind de la arborii binari ordonati sa se implementeze o structura de date cu urmatorii operatori:

	Adauga(k) - adauga elementul  k, daca acesta nu exista
	Sterge(k) - sterge elementul k
	RangulLui(k) - returneaza numarul elementelor mai mici sau egale cu k
	UrmatorulDupa(k) - returneaza  primul element mai mare decat k

Indicatii:

intr-un arbore binar ordonat, toate elementele din subarborele stang au cheile mai mici decat radacina si elementele din subarborele drept au cheile mai mari decat radacina. Deci, rangul radacinii este egal cu numarul elementelor din subarborele stang plus 1. Rangul unui nod oarecare din arbore, care corespunde cheii k, poate fi calculat in felul urmator: Daca k este mai mic decat radacina, rangul lui k in arbore este egal cu rangul lui k in cadrul subarborelui stang. Daca k este mai mare decat radacina, rangul sau in arbore va fi egal cu rangul sau in cadrul subarborelui drept plus rangul radacinii. Pentru a implementa eficient acest algoritm, nodul de arbore poate fi completat cu un contor reprezentand numarul de noduri din subarborele sau stang plus unu. Acest camp va fi actualizat corespunzator in timpul operatiilor de adaugare si stergere.

Realizarea operatorului UrmatorulDupa(k) nu implica modificari aduse structurii clasice de nod al unui arbore binar. Pentru a gasi primul element mai mare decat k, se realizeaza o cautare a lui k. in urma cautarii pot rezulta urmatoarele 3 situatii:

• k este gasit intr-un nod neterminal al arborelui. Urmatorul dupa k este cel mai mic nod al subarborelui sau drept
• procesul de cautare ajunge intr-o frunza cu cheia mai mare decat k. Aceasta va fi valoarea returnata
• procesul de cautare ajunge intr-o frunza cu cheia mai mica sau egala cu k; deci nodul cautat este cel mai recent intalnit nod pe drumul de la radacina inspre nodul curent unde cautarea a ales alternativa spre stanga.

7.8. Sa se implementeze un algoritm eficient de a tipari toate elementele unui arbore binar ordonat care au cheile cuprinse intre k1 si k2. Discutie asupra timpului de executie in termenii functiei O.

Indicatii

Procesul de cautare incepe cu radacina ca si nod curent. Daca nodul curent este mai mic decit k1, toate nodurile cautate se gasesc in subarborele drept; Daca nodul curent este mai mare decat k2, toate nodurile cautate se gasesc in subarborele stang. Daca nodul curent este intre k1 si k2, se va afisa nodul si se vor cerceta ambii subarbori (ordinea in care se fac acestea va determina ordinea in care se afiseaza elementele cautate).

7.9. Se da un arbore binar , in care fiecare nod contine, pe langa cheie, un camp numeric NR cu valori posibile intre 0 si adancimea nodului in arbore. Dati un algoritm care afiseaza, pentru fiecare nod, cheia celui de-al NR-lea stramos al sau. De exemplu, daca un nod are NR=1, se va afisa parintele sau; daca NR=2, se va afisa parintele parintelui sau, etc. Se va presupune ca arborele a fost construit corect, pentru fiecare nod campul NR avand o valoare valida.

Indicatii

Se va traversa arborele in preordine, mentinand intr-un tablou exploatat in maniera unei stive cheile stramosilor.