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:

${\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ż

Informacje w projektach siostrzanych

Multimedia w Wikimedia Commons

Definicje słownikowe w Wikisłowniku

• przechodzenie drzewa

Kontrola autorytatywna (abstrakcyjny typ danych):

• GND: 4145532-0