3.7. Strom

Obsah

3.7.1. Binární strom
3.7.2. Převod binárního stromu na text
3.7.3. Průchod binárním stromem
3.7.4. Binární vyhledávací strom
3.7.5. Stromy s neomezeným větvením
3.7.6. Reprezentace výrazu jako obecného stromu
3.7.7. Úlohy k řešení

Strom můžeme chápat jako zobecněný seznam, ve kterém může mít každý prvek více následníků. První prvek této struktury se nazývá kořen stromu, prvky bez následníků se označují jako listy. Uzlům, které nejsou listy, obvykle říkáme vnitřní uzly stromu. Stromy z pohledu matematiků a informatiků jsou poněkud zvláštní v tom, že se nejčastěji kreslí kořenem nahoru. Na Obr. 3.8 je znázorněn strom se sedmi uzly; kořenem je uzel 1, vnitřními uzly stromu jsou 1, 3 a 4 a listy jsou uzly 2, 5, 6 a 7.

Obrázek 3.8. Příklad obecného stromu

Strom patří do skupiny rekurzivních datových typů, neboť jeho definici lze popsat následujícími dvěma pravidly:

  1. Samostatný uzel bez následníků je strom.
  2. Uzel s alespoň jedním následníkem, který je stromem, je rovněž strom.

Obrázek 3.9. Strom jako rekurzivní datová struktura

Například uzel 1 z Obr. 3.8 má tři následníky - prvním je strom tvořený jediným uzlem 2, druhým následníkem je strom tvořený uzly 3, 5 a 6 a třetím následníkem je strom tvořený uzly 4 a 7 - viz Obr. 3.9.