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 dolaveho a dopraveho a vytvoríme podstromy s takto určenými počtami vrcholov.
|