În teoria graficelor , un copac înrădăcinat sau arborescență este un grafic aciclic direcționat având o singură rădăcină și astfel încât toate nodurile, cu excepția rădăcinii, să aibă un singur părinte.
În informatică , este, de asemenea, o structură de date recursivă utilizată pentru a reprezenta acest tip de grafic.
Într-un copac, există două categorii de elemente:
Rădăcina arborelui este singurul nod care nu are un părinte. Nodurile (tații cu fiii lor) sunt conectați între ei printr-o creastă . În funcție de context, un nod se poate referi la un nod (frunză) intern sau extern al arborelui.
Adâncimea unui nod este distanța, adică numărul de muchii, de la rădăcină la nodul. Înălțimea unui copac este cea mai mare adâncime a unei frunze pe copac. Dimensiunea unui arbore este numărul de noduri (numărare frunze sau nu), lungimea căii este suma adâncimilor fiecărei frunze.
Copacii pot fi etichetați. În acest caz, fiecare nod are o etichetă , care este un fel de „conținut” al nodului. Eticheta poate fi foarte simplă: un număr întreg, de exemplu. De asemenea, poate fi la fel de complex pe care îl doriți: un obiect, o instanță a unei structuri de date, un indicator etc. Este aproape întotdeauna obligatoriu să puteți compara etichetele în funcție de o relație de ordine totală , pentru a implementa algoritmii de pe copaci.
Fișierele și folderele dintr-un sistem de fișiere sunt de obicei organizate într-o structură de copac. Vezi de exemplu FHS .
Copacii sunt de fapt rar folosiți ca atare, dar există multe tipuri de copaci cu o structură mai restrictivă și sunt utilizați în mod obișnuit în algoritmi , în special pentru gestionarea bazelor de date sau pentru indexarea fișierelor. Acestea permit apoi căutări rapide și eficiente. Aici vă oferim principalele exemple:
Pentru a construi un arbore din cutii care conțin doar informații, puteți face una dintre următoarele trei modalități:
Observăm că există și alte tipuri de reprezentare specifice anumitor cazuri de copaci. De exemplu, heap-ul este reprezentat de o serie de etichete.
Cele Plimbările arbori sunt noduri vizite proces de un copac, de exemplu , pentru a găsi o valoare.
Calea de lățime corespunde unei căi în funcție de nivelul nodurilor arborelui. Un nivel este un set de noduri sau frunze interne situate la aceeași adâncime - vorbim și despre un nod sau frunză de aceeași înălțime în arborele luat în considerare. Ordinea de răsfoire a unui anumit nivel este de obicei conferită, recursiv, de ordinea de răsfoire a nodurilor părinte - noduri de la următorul nivel superior.
Astfel, dacă se utilizează arborele anterior, traseul va fi A , B , C , D , E , F și G .
Ruta în profunzime este un recursiv traseu pe un copac. În cazul general, sunt posibile două ordine:
Pentru arborii binari, putem face, de asemenea, o cale de infixare , adică tratarea nodului curent între nodurile stânga și dreapta. Astfel, dacă se utilizează arborele anterior, traseul va fi D , B , E , A , F , C și G .