Binárny strom

Riešenia


Úloha 17

void zrus(TVrchol *koren)
{
   if (koren != NULL){
     zrus(koren->ls);
     zrus(koren->ps);
     free((void*)koren);
   }
}

Pri rušení stromu je vhodné postupova od listov ku koreňu - teda metódou postorder (LPK). Strom zrušíme takto:

zrus(strom);
strom = NULL;

Úloha 18

void hladaj(TVrchol *koren, char *kto, TVrchol **ten)
{
    if (koren != NULL) {
      if (!strcmp(koren->meno, kto)){
         *ten = koren; /* našiel sa  ! */
      }
      else {
        hladaj(koren->ls, kto, ten);
        hladaj(koren->ps, kto, ten);
      }
    }
}

Okrem ukazovateľa na celý strom budeme teraz v hlavnom programe potrebova ešte ďalší ukazovateľ, ktorého hodnotou bude po skončení funkcie hladaj adresa nájdeného vrcholu resp. NULL v prípade, že sa taký vrchol v strome nenachádza.

TVrchol *ten = NULL;

hladaj(strom, "Hugo", &ten);
if (ten != NULL) printf("Nasiel sa! Je to naozaj %s", ten->meno);
else printf("Nenasiel sa !");

Skúste funkciu hladaj upravi tak, aby sa o nájdení príslušného vrchola, už ďalšie podstromy neprehľadávali. Nemáme však na mysli "násilné" ukončenie programu, ale vhodnú podmienku na vhodnom mieste :-) !


Úloha 19

TVrchol *vytvor(int n)  KLP
{
  TVrchol *novy;
  int x, dolaveho, dopraveho;

  if (n == 0) return(NULL);
  else {
     dolaveho = n / 2; dopraveho = n - dolaveho - 1;
     printf("prvok = ");
     scanf("%d", &x);
     novy = (TVrchol*)malloc(sizeof(TVrchol));
     novy->hodnota = x;
     novy->ls = vytvor(dolaveho);
     novy->ps = vytvor(dopraveho);
     return(novy);
   }
}

Rovnomerné pridávanie vrcholov do oboch podstromov je zabezpečené - z celkového počtu n vrcholov delením dvoma vypočítame hodnoty premenných dolavehodopraveho a vytvoríme podstromy s takto určenými počtami vrcholov.