Binární strom je hierarchická datová struktura , ve které každý uzel nemá více než dva potomky (děti). Obvykle se první uzel nazývá nadřazený uzel a potomci se nazývají levý a pravý potomek. Binární strom je uspořádaný řízený strom [1] .
Pro praktické účely se běžně používají dva podtypy binárních stromů – binární vyhledávací strom a binární halda .
Existuje následující rekurzivní definice binárního stromu (viz BNF ):
<binární strom> ::= ( <data> <binární strom> <binární strom> ) | nula .To znamená, že binární strom je buď prázdný, nebo se skládá z dat a dvou podstromů (každý z nich může být prázdný). Zřejmým, ale důležitým faktem k pochopení je, že každý podstrom je zase také strom. Pokud má uzel oba prázdné podstromy, pak se nazývá listový uzel (vrchol listu) nebo listový (terminální) uzel [2] .
Například znázorněno vpravo na obr. 1 strom podle této gramatiky by mohl být zapsán takto:
| (m (E (C (null null) nula ) (G nula (k null null) ) ) (s (p (o null null) (s null null) ) (y null null) ) ) |
Každý uzel ve stromu definuje podstrom , jehož je kořenem. Uzel m = (data, left, right) má dva potomky (levý a pravý) levý a pravý a podle toho dva podstromy (levý a pravý) s kořeny vlevo a vpravo [3] .
Mnoho užitečných datových struktur je založeno na binárním stromu:
| Strom (datová struktura) | |
|---|---|
| Binární stromy | |
| Samovyrovnávací binární stromy |
|
| B-stromy |
|
| předponové stromy |
|
| Binární dělení prostoru | |
| Nebinární stromy |
|
| Rozbití prostoru |
|
| Jiné stromy |
|
| Algoritmy |
|