REPREZENTAREA ARBORILOR BINARI
Dacă avem în vedere faptul că un arbore binar este un arbore, care înainte de toate este un graf, putem spune că printre metodele de reprezentare a arborilor binari se numără şi metodele de reprezentare a grafurilor, cum ar fi:
- reprezentarea prin matricea de adiacenţă;
- reprezentarea prin listele de adiacenţă;
- reprezentarea prin şirul muchiilor;
Modalităţile de reprezentare specifice arborilor binari sunt:
- reprezentarea standard:
1. Cu ajutorul vectorilor
2. Folosind alocarea dinamică
- reprezentarea cu ajutorul legăturilor Tata.
Reprezenarea cu ajutorul legăturii tata
Acest mod de reprezentare se realizează astfel:
- pentru fiecare nod, se precizează părintele său;
- pentru fiecare nod, se precizează ce fel descendent este, stâng sau drept, pentru părintele său.
OBSERVAŢIE!
Implementarea acestui mod de reprezentare, în cadrul unui program, se face folosind vectorii tata şi desc(desc=descendent), care au atâtea componente câte noduri are arborele, cu următoarele semnificaţii:
- tata[I]: reţine părintele nodului I, dacă acest există;
şi reţine 0, dacă nodul I nu are părinte(în cazul rădăcinii)
- desc[I]: -reţine valoarea -1, dacă nodul I este descendent stâng;
-reţine valoarea 1, dacă nodul I este descendent drept;
-reţine valoarea 0, dacă nodul I este rădăcina arborelui.