Arbori

Definitia 1: Se numeste Arbore cu rădacină = graf neorientat conex fără cicluri în care unul din noduri este desemnat ca rădăcină. Nodurile pot fi aşezate pe niveluri începând cu rădăcina care este plasată pe nivelul 1.

Rădăcină = Nod special care generează aşezarea unui arbore pe niveluri; Această operaţie se efectuează în funcţie de lungimea lanţurilor prin care celelalte noduri sunt legate de rădăcină.

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Descendent direct /  fiu = într-un arbore cu rădăcină nodul y este fiul (descendentul direct) nodului x dacă este situat pe nivelul imediat următor nivelului lui x şi există muchie între x şi y.

Ascendent = într-un arbore cu rădăcină nodul x este ascendentul nodului y dacă este situat pe un nivel mai mic decât nivelul lui y şi există un lanţ care le uneşte şi nu trece prin rădăcină.

Ascendent direct / părinte = într-un arbore cu rădăcină nodul x este părintele (ascendentul direct) nodului y dacă este situat pe nivelul imediat superior (cu număr de ordine mai mic) nivelului lui y şi există muchie între x şi y.

Fraţi = într-un arbore cu rădăcină nodul x este fratele nodului y dacă au acelaşi părinte.

Frunză =  într-un arbore cu rădăcină nodul x este frunză dacă nu are nici un descendent direct

Arbore cu rădăcină

- Nodul 1 este rădăcină. - Nodurile 5, 6, 7 sunt fii nodului 3. - Nodul 7 este părintele nodurilor 9 şi 10; - Nodul 9 este descendentul lui 3 - Nodul 3 este ascendentul lui 10 - Nodurile 8, 9 şi 10 sunt frunze - Nodurile 5, 6 şi 7 sunt fraţi.

Metode de memorare a arborilor

Cum un arbore este un caz particular de graf neorientat inseamna ca poate fi reprezentat ca un graf. De aici rezulta ca pentru reprezentarea unui arbore se pot utiliza:

1.        Metode specifice grafurilor:

-matricea de adiacenta

-liste de adiacente

2.        Metode specifice arborilor:

-prin legaturi de tip TATA. Arborele se reprezinta sub forma unui vector t cu n componente (n reprezinta numarul de noduri). Daca t[i]=k atunci nodul I este descendent al nodului k. Daca nodul I este varf atunci t[i]=0.

Fie arboreal din figura:

 unde nodul 1 este radacina.  Atunci vectorul de tip tata este:

0

1

1

1

3

3

3

4

7

7

Legatura de tip TATA se mai numeste si legatura cu referinte ascendente.

Legatura de tip TATA este determinata si de modul in care am ales nodul radacina. Spre exemplu daca vom considera nodul 4 ca fiind radacina vom obtine o alta solutie.

Metode de parcurgere:

Metodele de parcurgere sunt cele specifice grafurilor: in adancime si in latime.