Arbori-fisa de lucru 6

Probleme propuse:

1. Elevii unei clase stau in banca cate doi sau cate unul singur. Cand este nevoie sa se faca un anunt urgent la sfarsit de saptamana sau in vacanta, ei au stabilit un sistem prin care un elev va anunta pe altii doi care sunt colegi de banca, sau peunul singur, daca nu are coleg de banca (exista si elevi care nu vor da telefoane mai departe). Stiind ca doamna diriginta face primul anunt (anunta doi elevi care sunt colegi de banca) si apoi fiecare elev isi anunta alti doi colegi de banca (sauunul sau niciunul) de clasa si asa mai departe, se cere sa se scrie un program care realizeaza urmatoarele:

a) memorarea datelor intr-un arbore binar alocat in heap. Un elev inexistent se va marca cu *

b) numara si afiseaza din cati elevi este formata clasa

c) afiseaza numele tuturor elevilor din clasa

d) sa se determine daca un elev face parte din clasa

e) sa se afiseze elevii anuntati de diriginta

f) sa se afiseze cologii de banca (perechi)

g) numara cati elevi au acelasi nume cu un nume dat de la tastatura

h) afiseaza numele elevilor care nu mai au de anuntat pe nimeni

i) sa se afiseze colegul de banca al lui Gigel (sau un nume citit de la tastatura)

j) cine ar fi trebuit sa il anunte pe Dan (sau un nume citit de la tastatura)

k) sa se afiseze elevii care stau in stanga in banci

l) elevul x si elevul y isi schimba locurile. Sa se afiseze.

m) cate banci sunt ocupate de un singur elev

n) cate banci sunt ocupate de doi elevi

o) cate banci sunt ocupate

2. Un arbore binar retine numere intregi.

a) sa se afiseze numerele utilizand una dintre metode.

b) sa se afiseze numerele pare din arbore

c) sa se determine cel mai mare numar din arbore

d) sa se determine suma cifrelor tuturor numerelor din arbore

e) afisati frunzele

f) sa se determine daca exista o anumita valoare in arbore

g) sa se determine daca arborele contine numere prime

h) sa se genereze oglinditul arborelui

i) sa se afiseze subordonatii stangi

j) sa se inlocuiasca o cheie cu o alta

k) sa se inverseze doua chei

l) sa se afiseze fratele lui x

m) sa se afiseze tatal lui x

n) sa se afiseze fii (fiul) lui x

o) sa se determine minimul din arbore

p) sa se afiseze nodurile cu un singur subordonat

3. Sa se determine daca doi arbori sunt egali

4. Fie un arbore binar memorat prin vectorii stang si drept. Sa se parcurga arborele prin cele trei metode.

5. Fiind dat un arbore binar memorat in heap, sa se genereze un nou arbore binar identic cu primul.

6. Fie un arbore binar memora in heap. Sa se genereze oglinditul la dreapta al arborelui binar dat.

fig 1 fig 2

7. Fie un arbore binar memora in heap. Sa se afiseze cel de al k element din parcurgerea svd. Pt arborele din figura 1 pt k=3 se obtine 2

8. Fie un arbore binar memora in heap.

a) Sa se afiseze cate niveluri are arborele

b) Sa se afiseze nodurile de pe nivelul x

c) sa se afiseze nodurile pe niveluri

d) Calculati si afisati suma nodurilor de pe un nivel dat

e) sa se afisese frunzele care nu se gasesc pe ultimul nivel

9. Un arbore binar retine caractere.

a) sa se determine cate vocale retine arborele

b) se citeste un sir de caractere de la tastatura. Sa se determine daca sirul citit este egal cu sirul determinat de parcurgerea arborelui (svd, vsd sau sdv).

10. Sa se genereze un AB care reprezinta descompuneri in baza 2 ale numerelor <pow(2,k)

12. Fie un graf orientat memorat prin matricea de adiacenta. Sa se determine daca graful poate fi arbore binar. In caz afirmativ , pentru o solutie oarecare, sa se parcurga svd.

13. Fie un arbore binar. Sa se completeze arborele astfel incat fiecare nod sa aiba 2 subordonati. Valoarea cu care se face completarea se citeste de la tastatura.