9.  Stromy

9.2  Reprezentácia

Z  programátorského hľadiska je výhodné údajovú štruktúru strom definovať pomocou rekurzie:

Strom typu T je buď

• prázdna množina alebo
• vrchol typu T spolu s konečným počtom pripojených disjunktných stromov typu T, ktoré nazývame podstromy

Každý strom je tvorený ďalšími stromami, pre ktoré platí rovnaká definícia. Zviditeľníme ju na príklade binárneho stromu:

Na vedľajšom obrázku je vidieť, že aj podstrom sa skladá z koreňa a dvoch ďalších podstromov (niektorý z nich môže byť aj prázdny!). Každý list (t.j. vrchol bez synov) je tiež stromom, jeho ľavý aj pravý podstrom sú však prázdne.

Stromy sú najčastejšie reprezentované ako nelineárne zoznamy - pomocou ukazovateľov na synov. V každom uzle (vrchole) je okrem hodnoty aj toľko ukazovateľov na synov, koľko je stupeň stromu. Tento spôsob reprezentácie nie je veľmi efektívny, ak len malá časť vrcholov má maximálny počet synov. Preto sa takto implementujú najmä binárne stromy.

V binárnom strome má každý vrchol najviac dvoch synov - ľavého a pravého syna. Každý vrchol v strome bude teda záznam typu TVrchol, ktorý môžeme definovať takto:

typdef struct vrchol { char hodnota; struct vrchol *ls; struct vrchol *ps; } TVrchol; ls je ukazovateľ na ľavého syna ps je ukazovateľ na pravého syna Na sprístupnenie stromu potrebujeme ukazovateľ na koreň, v programe teda stačí deklarovať: TVrchol *strom; Ak niektorý vrchol nemá syna, hodnoty príslušných ukazovateľov sú NULL

Binárny strom sa dá v pamäti reprezentovať aj pomocou poľa! Ak očíslujeme vrcholy binárneho stromu a uložíme ich za radom ako prvky poľa, potom synovia vrcholu s indexom i sú v poli na pozíciách 2i a 2i + 1.