Drzewo binarne

Drzewo binarne – drzewo, w którym stopień każdego wierzchołka jest nie większy od 3.

Przykładowe drzewo binarne o rozmiarze 9 i wysokości 3

Ukorzenione drzewo binarne to drzewo binarne, w którym wyróżniono jeden z wierzchołków (zwany korzeniem) stopnia najwyżej 2.

W informatyce drzewo binarne to jeden z rodzajów drzewa (struktury danych), w którym liczba synów każdego wierzchołka wynosi nie więcej niż dwa. Wyróżnia się wtedy lewego syna i prawego syna danego wierzchołka.

Drzewo binarne, w którym liczba synów każdego wierzchołka wynosi albo zero albo dwa, nazywane jest drzewem regularnym. Przykładem takich drzew są drzewa Huffmana.

Szczególnymi odmianami drzew binarnych są drzewa BST, drzewa BSP oraz kopce binarne.

Własności

Liczba n-wierzchołkowych ukorzenionych drzew binarnych wynosi:

$b_{0}=1$

$b_{1}=1$

$b_{n}=\sum _{j=0}^{n-1}b_{j}b_{n-1-j}$

Istnieje też postać zwarta:

$b_{n}={\frac {1}{n+1}}{2n \choose n}$

znana jako rekursywna relacja Catalana.

Zobacz też

• przechodzenie drzewa