Drzewo binarne to rodzaj struktury danych używanej w programowaniu komputerowym do przechowywania, sortowania i uzyskiwania dostępu do informacji. Drzewa binarne są najprostszą odmianą drzewa, ale są bardzo przydatne i łatwe do wdrożenia. Typowa implementacja drzewa binarnego opiera się na węźle głównym połączonym z serią węzłów, które tworzą samo drzewo za pomocą zmiennych wskaźnikowych. Ten typ drzewa wywodzi swoją nazwę od faktu, że żaden węzeł w drzewie nie może mieć więcej niż dwoje dzieci.
Struktury danych drzewa występują w wielu odmianach. Składają się z różnych węzłów, które są zorganizowane według hierarchicznego wzorca. Pojedynczy węzeł, korzeń, jest punktem dostępu, przez który można przeszukiwać całe drzewo danych lub w inny sposób manipulować nim. Ten węzeł główny wskazuje na najwyższy węzeł w samym drzewie.
Każdy węzeł w drzewie, z wyjątkiem najwyższego węzła, będzie miał węzeł nadrzędny, który znajduje się nad nim w hierarchii drzewa. Może również mieć węzły podrzędne, które znajdują się poniżej. Dostęp do danego węzła uzyskuje się poprzez te znajdujące się nad nim w drzewie i zapewnia dostęp do tych znajdujących się pod nim.
Struktury danych w postaci drzewa binarnego pozwalają każdemu węzłowi mieć nie więcej niż dwoje dzieci. Dany węzeł może zatem mieć dołączone zero, jeden lub dwa węzły potomne. Zwykłe drzewa binarne pozwalają na węzły z dowolną liczbą dzieci w dowolnym punkcie drzewa. Nie nakładają również żadnych ograniczeń na sposób rozmieszczenia wartości przechowywanych w węzłach składających się na drzewo.
Struktury danych są najbardziej przydatne, gdy poprawiają szybkość, z jaką komputer może uzyskać dostęp do danych, a zmodyfikowane wersje drzew binarnych służą do poprawy ich wydajności. Drzewo wyszukiwania binarnego to takie, w którym wszystkie wartości danych znajdujące się w lewej gałęzi zstępującej z danego węzła mają wartości równe lub mniejsze od wartości przechowywanej w tym węźle. Wartości po prawej stronie węzła w uporządkowanym drzewie binarnym muszą z kolei być większe niż wartość w węźle podstawowym. Taka kolejność danych pozwala na napisanie znacznie wydajniejszego algorytmu wyszukiwania.
Kształt drzewa binarnego ma również znaczenie przy określaniu wydajności algorytmu wyszukiwania. Najmniej wydajna odmiana drzewa binarnego to taka, w której każdy węzeł ma tylko jedno dziecko. Komputer może potrzebować zbadać każdy element danych w całym drzewie, aby zlokalizować pojedynczą informację w tej konfiguracji. W przeciwieństwie do tego, najbardziej wydajne drzewo binarne to takie, w którym każdy węzeł, z wyjątkiem tych na dole drzewa, ma dwoje dzieci, a wszystkie węzły liści, dolne węzły drzewa, znajdują się w tej samej odległości od korzenia.