Data structure (Python)

In addition to the programming portion of the assignment, you will also be answering some questions about binary search trees. Some of the questions will require you to write your answers on the tree in empty_graph.pdf

. We will assume that any empty node boxes are non-existent nodes. For each of these problems, print out a copy of the blank tree, fill in the answers for the question, and please make sure to write the question number and your name on the sheet. If you know how to annotate PDF files directly, you can also do that instead of printing off the trees (this may be easier since you will have to submit a digital version of your solutions).

Question 1

Show the binary search tree built by adding numbers in this specific order, assuming the graph is empty to start with:  3, 63,  2, 89, 16, 24, 19, 30, 52, 24, 9, 4, 40 (You may need to add more boxes to the diagram).

Question 2

The trouble with binary search trees is that they can become unbalanced depending on the order that you insert values. Give an order for inserting the letters   I, P, A, F, W, Q, X, E,  G, N, S, B, Z such that the resulting tree is a complete binary search tree. Please make that your intermediate trees are also complete binary search trees as well. (Hint: it might be helpful to first draw the full/complete tree to figure out how the values must be arranged, then you can determine the order to add them.)

Question 3

· Part A: Given the following tree, Question3.pdf

, show the tree after removing the value 38.

· Part B: Using the tree produced by Part A, show the tree after removing the value 17.

Question 4

The computer has built the following decision tree for the Guess the Animal Game, Question4.pdf

. The player has an animal in mind and will answer the questions shown in the tree. Each of the player's responses is used to determine the next question to ask. For example, if the player is thinking of a sea turtle, she would answer Yes to the first (top) question, "does it live in the water?", which leads to the second question "is it a mammal?", to which she would answer No.

Show the decision tree that the computer should build after adding a Zergling and a question to differentiate it, "Does it eat space marines?", to the tree. The question and the animal should be added below existing questions in the tree. Note that Zerglings do eat space marines, do not live in the water, do not climb trees.