Submit twenty.c$,$ bst$.$c and bst$.$h to Gradescope.

Twenty Questions

Twenty questions is a parlor game in which one person thinks of something and the others need to guess what it is by asking questions that can be answered with a 'yes' or a $\text{'}$no$\text{'}.$ It became popular in the United States in the $19$th and $20$th centuries and became a popular radio and television game show. It encourages deductive reasoning and actually has applications in computer science and information theory. There is even a video game called Akinator which attempts to determine what fictional or real$-$life character, object, or animal a player is thinking of by asking a series of questions. It uses artificial intelligence to learn the best questions to ask the user via its experience.

Requirements for Twenty Questions $($about Fruits and Vegetables$)$

A program is needed to allow a person to play a guessing game with the computer. The user thinks of a fruit or vegetable and the computer asks questions that the user answers with a $\text{'}\backslash (($y$)\backslash )$ es$\text{'}$ or a $\text{'}\backslash (($n$)$ o $\backslash )\text{'}.$ The user wins if the computer cannot correctly guess the fruit$/$vegetable$.$

Bonus: If the computer loses, it prompts the user to enter a question that it could have asked to improve its chances of guessing correctly. It stores this question such that it can ask it in the future when it reaches this point in a game. In this way it can improve its performance. You don't need to implement this, but if you do it successfully then you will have the satisfaction of having done it successfully.

Design

A binary tree should be used to store the questions that the computer will ask. The leaf nodes should contain the names of fruits and vegetables while the inner nodes contain the questions. You should build the tree before the game starts. An example is shown below. You can reuse the code for the $($simple$)$ guessing game that we created for previous assignments. No file I$/$O or leaderboard functionality is required. Implementation

The program will be written in C$.$ Try to write your program incrementally by first creating the overall structure with empty functions $($stubs$)$ and testing often to see that your program is always working as expected. Use the code from our slides for the BST that uses recursion.

Testing

When testing, you are checking to see that the program satisfies the requirements.

Remember that when moving through the stages of requirements, design, implementation and testing, it is often necessary to go back to a previous stage and revisit decisions and make changes. It is always better to make design changes early in a project rather than later. Example tree:

$```$

struct node$*$ create$\_$game$\_$tree$()$

$\{$

struct node$*$ root $=$ NULL;

root $=$ insert$($root$,100,$ "Does it grow underground?", $"")$;

insert$($root$,50,"$Is it long in shape?", $"")$;

insert$($root$,25,"$Is it orange in color?", $"")$;

insert$($root$,15,"",$ "It's a carrot!"$)$;

insert$($root$,35,"",$ "It's a parsnip!"$)$;

insert$($root$,75,"$Is it red in color?", $"")$;

insert$($root$,65,"",$ "It's a radish!"$)$;

insert$($root$,85,"",$ "It's a potato!"$)$;

insert$($root$,150,$ "Does it grow on a tree?", $"")$;

insert$($root$,125,"$Is it red in color?", $"")$;

insert$($root$,115,"",$ "It's an apple!"$)$;

insert$($root$,135,"",$ "It's a peach!"$)$;

insert$($root$,175,"$Is it red in color?", $"")$;

insert$($root$,165,"",$ "It's a tomato!"$)$;

insert$($root$,185,""\text{'},$ "It's a pea!"$)$;

$\}$

return root;

int main$()$

$\{$

struct node$*$ game$\_$tree $=$ create$\_$game$\_$tree$()$;

printf$("$Welcome$!$ Press $\text{'}$q$\text{'}$ to quit or any other key to continue:

$")$;

char c$,$ game$\_$over $=0$;

$...$

$```$ Also, the node was defined in bst$.$h as:

$```$

struct node

$\{$

int data;

char$*$ question;

char$*$ guess;

struct node$*$ left;

struct node$*$ right;

$\}$;

$```$

That way the BST property can be used to order the nodes properly. Also, either the question or the guess will be an empty string $(""),$ so the program will know which to print for the user. Example run:

Welcome! Press $\text{'}$q$\text{'}$ to quit or any other key to continue:

x

You think of a fruit or vegetable and I will try to guess it$!$

Does it grow underground?

$\backslash (\backslash$mathrm$\{$y$\}/\backslash$mathrm$\{$n$\}\backslash )$ : y

Is it long in shape?

$\backslash (\backslash$mathrm$\{$y$\}/\backslash$mathrm$\{$n$\}\backslash )$ : n

Is it red in color?

$\backslash ($ y $/$ n $\backslash )$ : y

It's a radish!

$\backslash ($ y $/$ n: y $\backslash )$

I win!

Press $\text{'}\backslash ($ q $\backslash )\text{'}$ to quit or any other key to continue:

x

You think of a fruit or vegetable and I will try to guess it$!$

Does it grow underground?

$\backslash ($ y $/$ n $\backslash )$ : $\backslash ($ n $\backslash )$

Does it grow on a tree?

$\backslash (\backslash$mathrm$\{$y$\}/\backslash$mathrm$\{$n$\}\backslash )$ : y

Is it red in color?

y$/$n: y

It's an apple!

$\backslash (\backslash$mathrm$\{$y$\}/\backslash$mathrm$\{$n$\}\backslash )$ : n

You win!

Press $\text{'}\backslash ($ q $\backslash )\text{'}$ to quit or any other key to continue:

$\backslash ($ q $\backslash )$

Bye Bye!