W teorii wykres , A zakorzenione drzewa lub arborescence jest skierowany acykliczny wykres posiadające jeden główny, oraz tak, że wszystkie węzły z wyjątkiem korzenia mają jednego rodzica.
W informatyce jest to również rekurencyjna struktura danych używana do reprezentowania tego typu grafów.
W drzewie istnieją dwie kategorie elementów:
Korzeń drzewa jest jedynym węzłem, który nie posiada rodzica. Węzły (ojcowie z synami) są połączone ze sobą grzbietem . W zależności od kontekstu węzeł może odnosić się do wewnętrznego lub zewnętrznego węzła (liścia) drzewa.
Głębokość węzła to odległość, czyli liczbę krawędzi, od korzenia do węzła. Wysokość drzewa jest największa głębokość liścia na drzewie. Rozmiar drzewa jest jego liczba węzłów (licząc liści lub nie), długość ścieżki jest sumą głębi każdego z liści.
Drzewa można znakować. W tym przypadku każdy węzeł ma etykietę , która jest rodzajem „treści” węzła. Etykieta może być bardzo prosta: na przykład liczba całkowita. Może być również tak złożony, jak chcesz: obiekt, instancja struktury danych, wskaźnik itp. Prawie zawsze obowiązkowa jest możliwość porównania etykiet zgodnie z relacją całkowitego porządku w celu zaimplementowania algorytmów na drzewach.
Pliki i foldery w systemie plików są zwykle zorganizowane w strukturę drzewa. Zobacz na przykład FHS .
Drzewa są w rzeczywistości rzadko używane jako takie, ale istnieje wiele rodzajów drzew o bardziej restrykcyjnej strukturze i są one powszechnie używane w algorytmach , zwłaszcza do zarządzania bazami danych lub do indeksowania plików. Pozwalają na szybkie i skuteczne wyszukiwanie. Tutaj podajemy główne przykłady:
Aby zbudować drzewo z pudełek zawierających tylko informacje, możesz wykonać jeden z następujących trzech sposobów:
Zauważamy, że istnieją inne rodzaje reprezentacji specyficzne dla poszczególnych przypadków drzew. Na przykład sterta jest reprezentowana przez tablicę etykiet.
Na spacery drzewa są wierzchołki wizyty procesie drzewie, na przykład w celu znalezienia wartości.
Ścieżka szerokości odpowiada ścieżce według poziomu węzłów drzewa. Poziom to zbiór wewnętrznych węzłów lub liści położonych na tej samej głębokości - mówimy również o węźle lub liściu o tej samej wysokości w rozważanym drzewie. Kolejność przeglądania danego poziomu jest zwykle nadawana rekursywnie przez kolejność przeglądania węzłów nadrzędnych - węzłów następnego wyższego poziomu.
Tak więc, jeśli używane jest poprzednie drzewo, trasa będzie miała postać A , B , C , D , E , F i G .
Trasa pogłębiona to trasa rekurencyjna na drzewie. W ogólnym przypadku możliwe są dwa zamówienia:
W przypadku drzew binarnych możemy również wykonać ścieżkę infiksową , to znaczy traktować bieżący węzeł między lewym i prawym węzłem. Tak więc, jeśli używane jest poprzednie drzewo, trasa będzie D , B , E , A , F , C i G .