Arbori binari

In cazul in care o arborescenta are pentru fiecare varf cel mult doi descendenti, unul stang si unul drept, spunem ca avem un arbore binar. (prin abuz de limbaj, vom folosi termenul de arbore in loc de arborescenta).

Figura 1

In figura 1 este reprezentat un arbore binar in care radacina este 1 (s-a renuntat la orientarea arcelor, care sunt implicite deoarece se cunoaste radacina).

Observatii:

· Nodurile sunt asezate pe mai multe niveluri

· Radacina este pe nivelul 0

· Adancimea arborelui este egala cu numarul de niveluri-1. Arborele din figura 1 are 4 niveluri: nivel 0, nivel 1, nivel 2, nivel 3 si adancimea 3

· Se face distinctie intre descendentul stang si cel drept

Urmatorii doi arbori sunt distincti:

Modalitati de reprezentare a arborilor binari

1. Modalitati specifice grafurilor:

Fiind cazuri particulare de grafuri arborii binari se pot reprezenta ca si acestia prin:

• Matrice de adiacente
• Liste de adiacente

2. Modalitati specifice arborilor:

• Reprezentarea cu ajutorul vectorilor de tip tata
• Reprezentarea cu ajutorul a doi vectori: stang si drept . Pentru fiecrare nod i stang[i] retine numarul de ordine al nodului stang subordonat de i, iar drept[i] retine numarul de ordine al nodului drept subordonat de i. Daca nu exista nod subordonat, retine 0.

Pentru arborele din figura 1 cei doi vectori retin:

Vectorul stang:

2

4

6

0

0

0

0

0

Vectorul drept:

3

5

7

0

0

0

8

0

• Reprezentare in HEAP:

Utilizeaza alocarea dinamica a memoriei. Fiecare nod este reprezentat in HEAP ca o inregistrare care va retine numarul de ordine al nodului si adresele nodurilor subordonate stang si drept:

Struct nod{int nro;

nod* st, *dr;}

Generarea unui arbore binar utilizand HEAP-ul utilizeaza tehnica Divide et Impera. Vom defini un subprogram recursiv care intoarce adresa nodului curent. Pentru nodurile terminale se va citi 0 pentru subordonatii stang si drept sau numai un 0 daca lipseste unul dintre subordonatii unui nod. Subprogramul se autoapeleaza pentru fiecare dintre cei doi subordonati ai unui nod si intoarce adresa nodului curent. Pentru prelucrarea unui arbore binar este suficient sa se cunoasca adresa radacinii.

Pentru arborele din figura alaturata se vor introduce datela in urmatoarea ordine: 1 2 4 0 0 5 0 0 3 6 0 0 7 0 8 0 0

#include<iostream.h>

struct nod{int nro;

nod*st,*dr;};

nod *r;

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()

{

r=citire_h();

}

Memorare statica. Probleme propuse:

1. Sa se memoreze un arbore binar prin cele 3 metode specifice arborilor
2. In fisierul arbore.txt sunt scrise: pe prima linie numarul de noduri ale unui arbore binar si in continuare pe linii diferite vectorii stang si drept.
1. Sa se determine radacina arborelui binar
2. Sa se afiseze nodurile terminale
3. Cate noduri au un singur subordonat?
4. Sa se afiseze perechile de noduri care au acelasi ascendent
5. Sa se afiseze fii lui x
6. Sa se afiseze fratele lui x
7. Sa se determine daca x este descendent al lui y
8. Sa se determine „bunicul” lui x
9. Sa se determine „verii” lui x

3. Se citeste n numar natural. Sa se genereze un arboare binar in care se vor incarca valorile de la 1 la n. Trecerea la un nou nivel se va face dupa completarea nivelului precent. Arborele se va memora utilizand vectorii stang si drept. Radacina este 1. Sa se afiseze vectorii astfel obtinuti.

Ex pt n=8 se va genera:

4. Aceeasi problema ca la 3 cu diferenta ca arborele binar va fi memorat dinamic.
5. Un arbore binar este memorat prin vectorii stang si drept.
1. Sa se treaca arborele in vector de tip tata
2. Sa se genereze matricea de adiacente
3. Sa se genereze listele de adiacente
6. Sa se scrie un program care creeaza o lista liniara simplu inlantuita cu cheile unui arbore binar preluate pe nivele (mai intai nivelul 1, apoi nivelul 2 etc).