Diskrētās struktūras datorzinātnēs

1. Teorētiskais pamatojums
1.1 1. Uzdevums

Par koku sauc saistītu neorientētu grafu, kas nesatur ciklus. Divas fiksētas virsotnes savieno viena vienkārša ķēde.[1]

Koku apiešanas algoritmi ir procedūras, kas ļauj sistemātiski apmeklēt katru virsotni kokā ar sakni. Visbiežāk lieto 3 algoritmus: [2]
• Pirmssakārtojuma apiešana;
• Pēcsakārtojuma apiešana;
• Iekšēja apiešana;

Pirmssakārtojuma apiešana: [2]
Ir sakārtots koks ar sakni T un tam ir n apakškoki.
1.solis: Tiek apmeklēta koka sakne;
2.solis: Tiek apmeklēti visi apakškoki no kreisās puses pirmssakārtojuma manierē, turpina apmeklēt nākošos apakš kokus;
n+1. solis: Tiek apmeklēti Tn apakškoks.



Kokam veicot pirmssakārtojuma apiešanu iegūst prefiksu kodu, savukārt veicot pēcsakārtojuma apiešanu iegūst postfiksu kodu. To izmanto sarežģītu matemātisko izteiksmju aprēķināšanā.[2]
Prefiksa formu var novērtēt, ejot no labās uz kreiso pusi. Operators (operācijas zīme) atrodas pirms diviem operandiem. Lai iegūtu prefiksa formas vērtību, izpilda operāciju, ja operators atrodas pirms dieviem operandiem.[1]
Postfiksa formā operators seko aiz saviem diviem operandiem. Lai aprēķinātu postfiksa formas vērtību, strādā no kreisās uz labo pusi, izpildot operāciju, ja operators seko diviem operandiem.

Matemātisko izteiksmi izvieto kokā tā, ka strupceļa (galējās) virsotnes vienmēr attēlo operandus, bet iepriekšējās virsotnes – darbības jeb operācijas. [1]
…