Drzewo binarne

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

Drzewo binarne – drzewo, w którym stopień każdego wierzchołka jest nie większy od 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:

${\displaystyle b_{0}=1}$

${\displaystyle b_{1}=1}$

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

Istnieje też postać zwarta:

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

znana jako rekursywna relacja Catalana.

Zobacz też

• przechodzenie drzewa