Drzewo binarne w teorii grafów to drzewo, w którym stopień każdego wierzchołka jest nie większy od 3.
Ukorzenione drzewo binarne to drzewo binarne o stopniu nie większym niż 3, w którym wyróżniono jeden z wierzchołków (zwany korzeniem) stopnia 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.
Szczególnymi odmianami drzew binarnych są drzewa BST, drzewa BSP oraz kopce.
edytuj Własności
Liczba n-wierzchołkowych ukorzenionych drzew binarnych wynosi:
- b0 = 1
- b1 = 1
Istnieje też postać zwarta:
znana jako rekursywna relacja Catalana.
