Ješte než vytáhnete lano, sedák, karabiny, blokanty
a další lezecké propriety (bez kterých se asi neobejdete),
budete se se muset nad stromem zamyslet. Konkrétne nad stromem
binárním.
Stromová struktura
V informatice se stromové datové struktury používají pro
uchovávání dat. Jejich výhodou je vetšinou rychlé vyhledání
požadované informace. Každý typ stromu má presne
definovanou strukturu a zpusob vkládání, prohledávání a
odstranování záznamu.
Obr. 1: Stromové datové struktury
pripomínají stromy, proto se jim tak ríká:-)
Prevzato z
http://voho.cz/wiki/adt-strom/
Každá taková stromová struktura se skládá z uzlu,
které jsou propojeny hranami. Veškeré operace
zacínají v koreni stromu, kterým je jeden z uzlu. Koren je
jen jeden a nachází se úplne nejvýš (trošku,
zavádející, že?). Koren má vetšinou jednoho ci více
potomku (poduzlu), kterým je rodicem. Rodice a
potomka spojuje hrana. Potomci mohou mít další potomky - tím
se z nich stávají rodice. Uzel, který nemá další potomky se
nazývá list. Všichni potomci jednoho uzlu tvorí jeho
podstrom.
Použité termíny vysvetlené pomocí obrázku 2:
| koren stromu: |
F |
| uzly stromu: |
A, B, C, D, E, F, G, H, I |
| listy stromu: |
A, C, E, H |
| potomci uzlu B: |
A, D, C, E |
| rodic uzlu B: |
F |
| levý podstrom uzlu B: |
A |
Obr. 2: Príklad binárního
stromu
Prevzato z
http://cs.wikipedia.org.
Zpusoby vyhledávání (procházení stromu)
Procházení zacíná v koreni stromu a postupuje vždy na
potomky daného uzlu. Procházení koncí, když v ani jedné vetvi
(tj. v žádnem podstromu) není potomek.
Podle poradí, ve kterém se uzly prochází, se rozlišují tri
metody:
- Preorder
- proved akci na uzlu
- projdi levý podstrom
- projdi pravý podstrom
- Inorder
- projdi levý podstrom
- proved akci na uzlu
- projdi pravý podstrom
- Postorder
- projdi levý podstrom
- projdi pravý podstrom
- proved akci na uzlu
Akce na uzlu je v našem prípade zapsání obsahu uzlu.
Príklad procházení stromem na obrázku 2:
N
= navštívený uzel, L = levý, P = pravý
- Preorder (NLP): F, B, A, D, C, E, G, I, H
- Inorder (LNP): A, B, C, D, E, F, G, H, I
- Postorder (LPN): A, C, E, D, B, H, I, G, F
Volne zpracováno podle http://cs.wikipedia.org.
Finální souradnice
Vaším úkolem
je projít stromem na obrázku 3 metodou postorder a získat
souradnice jeho živého príbuzného ve formátu
ss°mm,mmm’.
Obr. 3: Projdi stromem metodou
postorder a najdi souradnice