Parcurgerea arborilor binari

Operatiile de parcurgere a arborilor binari se simplifica mult daca vom considera ca fiecare nod al arborelui subordoneaza un subarbore binar stang si un subarbore binar drept. Avand in vedere aceasta observatie se vor defini subprograme recursive care utilizeaza tehnica Divide et Impera.

Principalele modalitati de parcurgere ale unui arbore binar sunt:

A) Arborii binari pot fi parcursi prin metode specifice grafurilor: in adancime, latime.

B) Metode specifice arborilor binari :

• Parcurgerea in inordine (stanga –varf – dreapta SVD) – se parcurge mai intai subarborele stang, apoi varful, apoi subarborele drept.
• Parcurgerea in preordine (varf- stanga – dreapta VSD) – se parcurge mai intai varful, apoi subarborele stang, apoi subarborele drept.
• Parcurgerea in postordine (stanga – dreapta – varf SDV) – se parcurge mai intai subarborele stang, apoi subarborele drept si la sfarsit varful.

Solutiile de parcurgere ale arborelui din figura urmatoare :

parcurgere svd - in inordine 4 2 5 1 6 3 7 8 parcurgere vsd - in preordine 1 2 4 5 3 6 7 8 parcurgere sdv - in postordine 4 5 2 6 8 7 3 1

Programul urmator genereaza un arbore binar memorat in heap si il parcurge prin cele 3 metode.

#include<iostream.h>

#include<conio.h>

struct nod{int nro;

nod*st,*dr;};

nod *r;

void svd(nod *c)

{if(c)

{svd(c->st);

cout<<c->nro<<" ";

svd(c->dr);

}

}

void vsd(nod *c)

{if(c)

{cout<<c->nro<<" ";

vsd(c->st);

vsd(c->dr);

}

}

void sdv(nod *c)

{if(c)

{sdv(c->st);

sdv(c->dr);

cout<<c->nro<<" ";

}

}

nod* citire_h()

{int nr;

nod*c;

cout<<"nr de ordine ";

cin>>nr;

if(nr)

{c=new nod;

c->nro=nr;

c->st=citire_h();

c->dr=citire_h();

return c;

}

else

return 0;

}

void main()

{clrscr();

r=citire_h();

cout<<endl<<"parcurgere svd - in inordine "<<endl;

svd(r);

cout<<endl<<"parcurgere vsd - in preordine "<<endl;

vsd(r);

cout<<endl<<"parcurgere sdv - in postordine "<<endl;

sdv(r);

getch();

}

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 pe unul 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 (sau unul 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.