Datu struktūru, kurā elementu sasaistes raksturs ir “viens ar vairākiem” (one-to-many), sauc par koku (tree) jeb hierarhisku datu struktūru. Hierarhisks nozīmē to, ka datu struktūras elementi izvietoti vairākos līmeņos.
Kokus var klasificēt kā bināros kokus, kurus savukārt var dalīt binārās meklēšanas kokos, sabalansētos kokos(AVL koki, sarkanmelnie koki u.c.) un kaudzēs (heap), un B-kokos.
Visbiežāk lieto bināros kokus, kuros katrai virsotnei nav vairāk kā 2 pēcteči. Katrs pēctecis ir kreisais bērns vai labais bērns. Virsotnes (node) kokā savienotas ar šķautnēm (edge). Tātad binārais koks ir koks, kurā:
1. No vienas virsotnes iziet ne vairāk par diviem lokiem;
2. katrs apakškoks ir identificējams kā kreisais vai labais;
3. koks var būt tukšs;
4. katram koka elementam izņemot sakni ir priekštecis;
Organizējot datu struktūru saistītā formā attēlotajā binārajā kokā, katram elementam jāsatur norādes gan uz koka sakni, gan uz tekošo elementu. To realizē, izmantojot divas Pointer norādes, kas satur atbilstošo Labo vai Kreiso bērnu adreses. Ja dotajam elementam nav bērnu vai vecāku, norāde nenorāda ne uz ko, jeb norāde ir uz NIL.
Binārā koka struktūra paredz, ka katram koka elementam ir jāglabā kāda informācijas vienība. Katram elementam jāsatur arī atslēgas lauks, pēc kura tas ir identificējams. Elements var tikt atrasts arī pēc atslēgas. …