Definícia
Strom je označenie pre dôležitú dynamickú štruktúru. Stromy sa používajú v prípade hierarchických vzťahov a
rekurzívnych štruktúr objektov.
Je definovaný nasledujúcim spôsobom: Štruktúra strom so základným typom T je buď prázdna štruktúra,
alebo vrchol typu T spolu s konečným počtom pripojených disjunktných stromových štruktúr so základným
typom T, ktoré nazývame podstromy.
Strom je vo svojej podstate súvislý, acyklický a neorientovaný graf. Keď je neorientovaný graf síce acyklický,
ale môže byť rozložený do viacerých komponentov, voláme ho les.
- 1. G je strom.
- 2. Ľubovolné dva vrcholy v G sú spojené jedinou jednoduchou cestou.
- 3. G je súvislý, ale keď sa odoberie ľubovolná hrana z E, výsledný graf nie je spojitý.
- 4. G je súvislý a |E| = |V|-1.
- 5. G je acyklický a |E| = |V|-1.
- 6. G je acyklický, ale keď sa pridá do E ľubovolná hrana, výsledný graf obsahuje cyklus.
Vlastnosti
Usporiadaný strom je taký, v ktorom sú vetvy každého vrcholu usporiadané. Z toho vyplýva,
že napríklad dva stromy na obrázku v časti vizualiácia sú rozdielne objekty. Vrchol y, ktorý je
bezprostredne pod vrcholom x, sa nazýva (priamy) nasledovník vrcholu x.
Ak existuje hrana z vrcholu u do vrcholu w, tak potom u
je otcom w a w je synom
u.
Ak je vrchol x
na i-tej úrovni, tak y bude na (i+1)-tej úrovni.
O vrchole x potom hovoríme, že je priamy
predchodca vrcholu y. Koreň stromu je na nultej úrovni. Maximálna úroveň ľubovolného prvku
v strome sa volá hĺbka alebo výška.
Ak nejaký prvok nemá nasledovníkov, nazýva sa koncový prvok alebo list stromu. Prvok,
ktorý nie je listom, nazývame vnútorným vrcholom. Počet (priamych) nasledovníkov vnútorného
vrcholu nazývame jeho stupňom. Maximálny stupeň spomedzi všetkých vrcholov určuje stupeň stromu.
Počet vetiev (hrán) alebo vrcholov, ktoré treba prejsť, aby sme sa dostali od koreňa k vrcholu
x sa nazýva dĺžka cesty vrcholu x. Vo všeobecnosti platí, že dĺžka cesty vrcholu na
i-tej úrovni
sa rovná hodnote i. Dĺžka cesty celého stromu je definovaná ako súčet dĺžok ciest jednotlivých
vrcholov stromu.
Reprezentácia stromov
Keďže stromy sú rozvetvené rekurzívne štruktúry je výhodné na ich reprezentáciu použiť smerníky.
Nemá ale zmysel definovať premenné s pevnou stromovou štruktúrou. Vrcholy stromu sú preto definované
ako premenné s pevnou štruktúrou, teda pevne stanoveného typu a kde stupeň stromu určuje počet smerníkov
na podstromy daného vrcholu. Odkaz na prázdny strom sa vyjadruje konštantou nil.
Stromy sa dajú reprezentovať aj ako pole záznamov (array of record), kde každý záznam obsahuje
relevantné informácie ohľadom vrchola.
Vizualizácia
Na obrázkoch je rôznymi spôsobmi zobrazený ten istý strom. Najprv je to pomocou uzátvorkovného zápisu, potom pomocou množinových
diagramov a nakoniec pomocou najčastejšieho grafického zobrazenia.
Ak je strom usporiadaný, nasledujúce stromy sú dva rôzne objekty.
Reprezentácia výrazu (a+b/c)*(d-e*f) a reprezentácia toho istého výrazu v strome ako dátovej štruktúre vyjadrenej pomocou smerníkov.
