Build a program capable of guessing what a user is thinking. Our program will ask the user to think of their favorite cartoon/television/movie character and then attempt to guess what they are thinking based on the answers to a series of questions. The program will use the users responses to build a decision tree and eventually become smart enough to correctly guess the users thought.

Here is an example run:

$ ./a.out

Are you thinking of a your favorite character? (yes/no) yes

Is it Captain America? (yes/no) no What is the character's name? The Doctor What would distinguish The Doctor from Captain America? Do they own a Tardis If the character were The Doctor the answer would be? (yes/no) yes

Are you thinking of a your favorite character? (yes/no) yes

Do they own a Tardis? (yes/no) no Is it Captain America? (yes/no) no What is the character's name? The Hulk What would distinguish The Hulk from Captain America? Do they like the color green If the character were The Hulk the answer would be? (yes/no) yes

Are you thinking of a your favorite character? (yes/no) yes

Do they own a Tardis? (yes/no) no Do they like the color green? (yes/no) yes Is it The Hulk? (yes/no) yes I rule!

Are you thinking of a your favorite character? (yes/no) no

$

As you can see, the program starts by guessing a random character and then asks the user for more information. Eventually, it learns enough to make correct guesses off a series of yes/no responses from the user.

The Program:

The program starts each round by asking the first question stored at the top (root) of the tree. Depending on the answer, it traverses left or right, asking questions, until a leaf node is reached. At this point the program needs to make a guess because there are no more paths to follow. Nothing needs to be done if the program guesses correctly. However, if the program guesses incorrectly It must ask for the name of a character and a new question to asked in order to distinguish this new character from the wrong guess. It then adds a new leaf node to the tree containing the name of the new character and also adjusts this nodes parent to contain the question specified by the user.

Here is some pseudo code:

While the user is thinking of a character:

Start at root

While the left child is not a leaf node: If user responds yes to question in current node: Follow right child Else: Follow left child

Make a guess using the character stored in the current node

If guess is correct: Print success message Move to next iteration of loop

Prompt user for the new characters name Prompt user for question that distinguishes the new user from the incorrect guess

Insert question into current node

Prompt user for answer to the question they answered

If answer is yes: Set left child equal to guess Set right child equal to character Else: Set left child equal to character Set right child equal to guess 1

Requirements:

Write a class called CharacterTree that handles building and accessing your decision tree. The only requirement of this class is that is uses some sort of linear or dynamic array to store the tree itself. DO NOT USE STRUCTS OR CLASS OBJECTS. Refer to the heap lecture for more information on representing tree-like structures as linear arrays.

Suggestions:

#include #include

getline(cin, )

void CharacterTree::insert( string s, int index){} string CharacterTree:retrieve( int index ){}