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.