9.  Stromy

9.4  Binárny strom - príklad

  Typickým príkladom binárneho stromu je vlastný rodokmeň. Jednotlivé vcholy tohto stromu predstavujú členov rodiny (informácie o nich - napr. meno, rok narodenia, zamestnanie a pod.)

Namiesto ľavého a pravého syna každého vrcholu by sme mali vlastne hovoriť o matke a otcovi.

Napíšeme postupne funkcie, pomocou ktorých budeme s naším rodokmeňom pracovať. Budeme predpokladať, že žiadny dvaja naši príbuzní nemajú rovnaké meno (pre jednoduchosť). Definujme si najskôr typ vrcholu:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct vrchol {
   char meno[20];        /* meno */
   struct vrchol *ls;    /* otec  */
   struct vrchol *ps;    /* matka */
} TVrchol; 

TVrchol *strom = NULL;

Náš strom je zatiaľ prázdny. Vytvorme teda prvý vrchol - koreň stromu:

strom = (TVrchol*)malloc(sizeof(TVrchol));
strcpy(strom->meno, "ja");
strom->ls = NULL;
strom->ps = NULL;

Alebo si rovno pripravme funkciu na vytvorenie nového vrcholu - bude vracať ukazovateľ na vytvorený vrchol:

TVrchol *novy(char *kto)
{
   TVrchol *pom = (TVrchol*)malloc(sizeof(TVrchol));
   pom->ps = NULL;
   pom->ls = NULL;
   strcpy (pom->meno, kto);
   return(pom);
}

Teraz by sme chceli do stromu pridať ďalších členov rodiny. Každý nový prvok pridáme na správne miesto - t.j. ako ľavého alebo pravého syna určeného vrcholu.

void pridaj(TVrchol *koren, char *komu, char *kto, char syn)
{ 
  if (!strcmp(koren->meno, komu)) { 
    if (syn == 'P') 
      if (koren->ps != NULL) printf("Dany vrchol uz existuje!");
      else koren->ps = novy(kto);
		 
    if (syn == 'L') 
      if (koren->ls != NULL) printf("Dany vrchol uz existuje!");
      else koren->ls = novy(kto);
  }
  else {
    if (koren->ls != NULL) pridaj(koren->ls, komu, kto, syn);
    if (koren->ps != NULL) pridaj(koren->ps, komu, kto, syn);
  }
}

  Funkcia strcmp porovnáva dva reťazce. Ak sú rovnaké, vráti hodnotu 0!

Pridajme teda do stromu ďalší vrchol:

pridaj(strom,"ja","mama",'L');

Čo sa udeje? V strome hľadáme vrchol s hodnotou "ja" ktorému máme ako ľavého syna pridať nový vrchol s hodnotou "mama". Všimnite si, že strom prehľadávame metódou KLP. Ak hľadaný vrchol nájdeme a zistíme, že už ľavého syna má, vypíšeme o tom oznam na obrazovku.

Pridajme do stromu ďalších:

pridaj(strom,"ja","otec",'P');
pridaj(strom,"otec","dedko2",'P');
pridaj(strom,"otec","babka2",'L');

atď.

Vytvorený rodokmeň ("rodostrom") samozrejme chceme zviditeľniť:

void vypis(TVrchol *koren)   LKP
{
   if (koren != NULL) {
     vypis(koren->ls);
     printf("%s  ", koren->meno);
     vypis(koren->ps);
   }
}

Precvičme si

  Napíšte funkciu, ktorá nám umožní zrušiť naraz celý strom (uvoľniť pamäť alokovanú pre jednotlivé vrcholy stromu).

  Napíšte funkciu, ktorá nám umožní zistiť, či sa v našom rodokmeni nachádza človek s daným menom (nájde daný vrchol). Po skončení tejto funkcie chceme mať navyše k dispozícii aj ukazovateľ na príslušný vrchol.

  Pri konštrukcii stromu je ideálne, ak má minimálnu výšku (vyhľadávnie je efektívnejšie). Na to je potrebné, aby sme na každej úrovni, s výnimkou poslednej, umiestnili maximálny počet vrcholov. Skonštruujeme takto tzv. dokonale vyvážený strom, v ktorom pre každý vrchol platí, že počet vrcholov v jeho ľavom a pravom podstrome sa líši najviac o jednotku.

Napíšte funkciu, ktorá z n vstupných hodnôt vytvorí binárny strom, ktorý bude dokonale vyvážený. Jednotlivé vrcholy umiestnite rovnomerne do ľavého a pravého podstromu! Pracujte so stromom celých čísel.