4. Nerovnoměrné kódy

4.2. Binární strom

Existují různé způsoby konstrukce prefixových kódů, z nichž si postupně tři představíme. V prvním z nich využijeme ke konstrukci binární strom. Jeho základem je kořen (uzel), ze kterého vychází dvě větve (hrany) na různé strany. Jeden směr v celém stromu značíme 0, druhý 1.

základ binárního stromu.
Obr. 15: Kořen a první patro binárního stromu.

Každá z těchto větví se stejným způsobem může rozdvojit v dalším uzlu. Uzly označujeme kódovými slovy, která reprezentují cestu, kterou jsme k nim ve stromu po hranách dorazili od kořene. Uzly, ze  kterých již další větve nevedou, nazýváme listy.

Tvorba prefixového kódu pomoci binárního stromu je založena na dvou předpokladech:

  1. Známe délku kódových slov, která má kód obsahovat.
  2. Kódová slova jsou ve stromu listy.

  Jak sestavíte binární strom prefixového kódu, jehož kódová slova mají mít postupně délku 2, 1, 3?