Use the knowledge we know about trees to 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 tehn attempt to guess what tehya re 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 of a series of yes/no responses from the user. A decision tree is a binary tree where typically the left child is followed after receiving a no and the right child is followed after receiving a yes according to the users response to the question stored in the parent node. For example, the decision tree for the example shown above might look something like this: Each node contains a question to ask a user and two pointers referencing the left and right children of the node. 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 ask 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 ){}