Graf, który nie zawiera ani jednego cyklucyklcyklu oraz jest spójnygraf spójnyspójny, nazywamy drzewem. Każdy jego wierzchołek określa się mianem węzła. Jeśli drzewo zawiera jeden wyróżniony wierzchołek zwany korzeniem, wówczas nazywamy je drzewem ukorzenionym. Tego typu drzewa zazwyczaj przedstawiane są tak, że ich korzeń znajduje się na górze.

Drzewa należą do struktur danych drzewiastych, co oznacza, że krawędzie łączą wierzchołki w taki sposób, że między dwoma dowolnymi wierzchołkami istnieje zawsze tylko jedna droga.

Słownictwo stosowane do opisu części drzew jest swego rodzaju kombinacją terminologii genealogicznej oraz nazewnictwa z zakresu botaniki. Weźmy pod uwagę węzeł $v$ drzewa ukorzenionego $T$, w którym korzeniem jest $r$. Każdy węzeł $s$ na drodze z $r$ do $v$ (gdzie $s≠v$) nazywany jest przodkiem węzła $v$. A jeśli $s$ jest ojcem $v$, to $v$ jest z kolei potomkiem węzła $s$.

Przeanalizujmy to na przykładzie zaprezentowanego drzewa. Dane jest drzewo, którego korzeń to węzeł o kluczu 9. Wszystkie węzły na drodze do węzła o kluczu 17 – czyli węzły o kluczach 12 oraz 15 – są przodkami węzła o kluczu 17. Węzeł o kluczu 17 jest potomkiem tych węzłów.

Węzły połączone są krawędziami (na ilustracji są to linie).

R1X4cECpMb68E

Ilustracja przedstawia budowę drzewa binarnego z zaznaczonymi nazwami elementów.
Wierzchołki zapisane są w okręgu.
Napis korzeń wskazuję strzałką w dół na wierzchołek 9.
Wierzchołek posiada 2 rozgałęzienia w lewo i prawo.
Po prawej łączy się z wierzchołkiem 5.
Wierzchołek 5 łączy się z wierzchołkami 3, i 7.
Wierzchołek 3 łączy się z wierzchołkami: 1, 4.
Wierzchołki 3, 1, 4 zaznaczone są trójkątem i podpisane: poddrzewo.
Wierzchołek 7 połączony jest z wierzchołkiem 8.
Z lewej strony korzeń połączony jest z wierzchołkiem 12, który jest podpisany jako ojciec.
Wierzchołek 12 łączy się z wierzchołkami 11 i 15, które podpisane są jako bracia.
Wierzchołek 15 łączy się z wierzchołkiem 17.
Wierzchołki na dole drzewa bez żadnego dalszego połączenia: 1, 4, 8, 11, 17 podpisane są jako liście.

Jeśli ostatnią krawędzią drzewa $T$ na drodzedrogadrodze od korzenia $r$ do węzła $v$ jest $sv$, to $s$ jest ojcem węzła $v$, a $v$ synem węzła $s$. Jeśli dwa węzły mają tego samego ojca, nazywamy je braćmi. Z kolei węzeł, który nie ma synów, zwany jest liściem drzewa (lub węzłem zewnętrznym).

Przeanalizujmy to na przykładzie zaprezentowanego drzewa. Dane jest drzewo, którego korzeń to węzeł o kluczu 9. Załóżmy, że ostatnią krawędzią tego drzewa na drodze od węzła o kluczu 9 do węzła o kluczu 15 jest krawędź łącząca węzły o kluczach 12 oraz 15. W takiej sytuacji węzeł o kluczu 12 jest ojcem węzła o kluczu 15. Równocześnie węzeł o kluczu 15 jest synem węzła o kluczu 12. Węzły o kluczach 11 oraz 15 mają wspólnego ojca, czyli są braćmi. Natomiast liściem drzewa, czyli węzłem, który nie ma synów, jest węzeł o kluczu 17.

Drzewa binarne

Drzewo binarne to szczególny rodzaj drzewa ukorzenionego, w którym każdy węzeł ma maksymalnie dwóch synów. Relacje ojców z synami implementuje się za pomocą struktur z dowiązaniami. W takiej strukturze każdy węzeł jest obiektem, który zawiera następujące trzy pola:

1. klucz – klucz węzła, przechowywana przez węzeł wartość,

2. lewy – wskaźnik do lewego syna,

3. prawy – wskaźnik do prawego syna.

W przypadku, gdy węzeł nie ma lewego bądź prawego syna, odpowiednie pole lewy lub prawy wskazuje na Null. W przypadku zaprezentowanego drzewa węzeł o wartości klucza równej 4 jest pozbawiony syna.

W drzewach binarnych położenie węzłów ma znaczenie. Lewy syn zawsze jest położony na lewo od ojca, prawy syn – na prawo.

W problematyce drzew binarnych definiujemy takie terminy, jak:

• głębokość węzła – liczba krawędzi na drodze od korzenia do węzła;

• wysokość drzewa binarnego – maksymalna głębokość wśród wszystkich węzłów w drzewie; liczba krawędzi w najdłuższej ścieżce, której początkiem jest korzeń;

• wysokość węzła – różnica wysokości drzewa binarnego i głębokości węzła;

• lewe poddrzewo węzła – drzewo binarne, którego korzeniem jest lewy syn węzła;

• prawe poddrzewo węzła – drzewo binarne, którego korzeniem jest prawy syn.

Słownik