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.