Binárne stromy sú zovšeobecnenie spojkových zoznamov. Každý uzol binárneho vyhľadávacieho stromu má namiesto jedného smerníka na ďalší prvok až dva smerníky. Vďaka tomu je vhodný na reprezentáciu informácií ktoré majú hierarchický charakter - napr. sada otázok v znalostnom systéme. Ak na každú otázku sú iba dve možné odpovede, tak je možné ich zoradiť do štruktúry podobnej stromu. Na začiatku (v koreňovom uzle) bude uložená prvá otázka. Všetky ďalšie otázky budú uložené v podradených stromoch. Otázka sa zobrazí podľa toho, ako používateľ odpovedá ,

V binárnom vyhľadávacom strome poznáme dva druhy uzlov: vnútorný (nelistový) uzol a listový uzol. Listový uzol je taký, ktorý neobsahuje odkazy na žiadne ďalšie uzly. Vnútorný uzol obsahuje odkazy na iné listové alebo nelistové uzly. V našom znalostnom systéme sú nelistové uzly otázky a listové uzly finálne rozhodnutia znalostného systému.

struct tree {
   // Otázka aleo odpoveď
   char value[SIZE];
   // Odpoveď áno
   struct tree* left;
   // Odpoveď nie
   struct tree* right;
};

Smerníky left alebo right hovoria, čo má chatbot radiť ak používateľ odpovie na otázku áno (left) alebo nie (right).

Prvú otázku si vytvorím klasickým spôsobom. Ak sú oba smerníky nulové, ide o listový uzol.

struct tree* chatbot = calloc(1,sizeof(struct tree));
strcpy(chatbot->value,"Je to ovocie alebo zelenina?");

Do ľavého a do pravého podstromu si môžme uložiť ďalšie otázky alebo odpovede. Ak chceme rozlišovať medzi dvoma druhmi ovocia a zeleniny, poznačíme si ich do listových uzlov a tie napojme na koreňový uzol. Takto zmeníme listový uzol na vnútorný a na otázku napojíme odpovede.

struct tree* mrkva = calloc(1,sizeof(struct tree));
strcpy(mrkva->value,"*Mrkva");
struct tree* jablko = calloc(1,sizeof(struct tree));
strcpy(mrkva->value,"*Jablko");

chatbot->left = jablko;
chatbot->right = mrkva;

Výsledný strom bude vyzerať nejako takto:

Ak chceme rozlišovať medzi troma druhmi ovocia alebo zeleniny, musíme na vhodné miesto vložiť ďalšiu otázku:

struct tree* mrkva = calloc(1,sizeof(struct tree));
strcpy(mrkva->value,"*Mrkva");
struct tree* kalerab = calloc(1,sizeof(struct tree));
strcpy(mrkva->value,"*Kalerab");
struct tree* jablko = calloc(1,sizeof(struct tree));
strcpy(mrkva->value,"*Jablko");
struct tree* zelena = calloc(1,sizeof(struct tree));
strcpy(zelena->value,"Je zelenej farby?");

chatbot->left = jablko;
chatbot->right = zelena;
zelena->left = kalerab;
zelena->right = mrkva;

Vznikne nám toto:

Previous Post