You may have seen online games that purport to be psychic, with the ability to correctly guess any item or character that you may be thinking of by asking yes/no questions of the player. Your goal is to write a program that can play this game, in part by learning about a universe of your choice as it plays by asking yes/no questions. For example, your program might learn about animals by having the following dialogue with its user. (For readability, user responses are shown here in red. The responses also use capital letters, which is not a requirement for this assignment.) Think of an animal, and I will guess it. Does it have legs? YES Is it a cat? YES I win! Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Is it a snake? YES I win! Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Is it a snake? NO I give up. What is it? EARTHWORM Please type a question whose answer is yes for earthworm and no for snake: DOES IT LIVE UNDERGROUND? Continue? YES Think of an animal, and I will guess it. Does it have legs? NO Does it live underground? NO Is it a snake? NO I give up. What is it? FISH Please type a question whose answer is yes for fish and no for snake: DOES IT LIVE IN WATER? Continue? NO Good-bye. The program begins with minimal knowledge about animals: It knows that cats have legs and snakes do not. When the program incorrectly guesses snake the next time, it asks for the answer and also asks for a way to distinguish between snakes and earthworms. The program builds a binary tree of questions and animals. A YES response to a question is stored in the questions left child; a NO response to a question is stored in the questions right child. Task Extend the LinkedBinaryTree class to create a data structure that supports this game. Make use of the protected methods in LinkedBinaryTree to modify the tree structure. You may name your class anything you wish, though your module must be named twenty.py. Additionally, you must have a play_game() function in the module (not your class) that allows the user to play when it is called. When the game ends, you should offer the player the opportunity to save the data in the tree so that they do not have to re-train your program from scratch every time. When starting the game, you should give an option to load a saved game. Make use of the save_tree() and load_tree() methods in BinaryTree to save and load the game from a file. You should not modify these methods, just call them.

tree.py code

class Tree:

"""Abstract base class representing a tree structure"""

#-------------------- nested Position class ---------------------

class Position:

"""An abstraction representing the location of a single element"""

def element(self):

raise NotImplementedError('Must be implemented by subclass')

def __eq__(self, other):

"""Return True if other Position represents the same location"""

raise NotImplementedError('Must be implemented by subclass')

def __ne__(self, other):

"""Return True if other does not represent the same location"""

return not(self == other)

#--- abstract methods that concrete subclass must support -----------

def root(self):

"""Return Position representing the tree's root (or None if empty)"""

raise NotImplementedError('Must be implemented by subclass')

def parent(self, p):

"""Return Position representing p's parent (or None if p is root)"""

raise NotImplementedError('Must be implemented by subclass')

def num_children(self, p):

"""Return the number of children that p has"""

raise NotImplementedError('Must be implemented by subclass')

def children(self, p):

"""Generate an iteration of Positions representing p's children"""

raise NotImplementedError('Must be implemented by subclass')

def __len__(self):

"""Return the total number of elements in the tree"""

raise NotImplementedError('Must be implemented by subclass')

#--- concrete methods implemented in this class --------------------

def is_root(self, p):

"""Return True if Position p represents the root of the tree"""

return self.root() == p

def is_leaf(self, p):

"""Return True if Position p does not have any children"""

return self.num_children(p) == 0

def is_empty(self):

"""Return True if the tree is empty"""

return len(self) == 0

# -------------- traversal methods ---------------------------------

def preorder(self):

"""Generate a preorder iteration of positions in the tree"""

if not self.is_empty():

for p in self._subtree_preorder(self.root()): # Start recursion

yield p

def _subtree_preorder(self, p):

yield p # Visit p before its subtrees

for c in self.children(p): # For each child c

for other in self._subtree_preorder(c): # Do preorder of c's subtree

yield other # Yielding each

def postorder(self):

if not self.is_empty():

for p in self._subtree_postorder(self.root()):

yield p

def _subtree_postorder(self, p):

for c in self.children(p): # For each child c

for other in self._subtree_postorder(c): # Do postorder of c's subtree

yield other # Yielding each

yield p # Visit p after its subtrees

binary_tree.py code

from tree import Tree

import pickle # Special, used for saving and loading the tree from a file

class BinaryTree(Tree):

"""Abstract base class representing a binary tree structure"""

#---------- additional abstract methods ---------------

def left(self, p):

"""Return a Position representing p's left child.

Return None if p does not have a left child.

"""

raise NotImplementedError('Must be implemented by subclass')

def right(self, p):

"""Return a Position representing p's right child.

Return None if p does not have a right child.

"""

raise NotImplementedError('Must be implemented by subclass')

# ---------- concrete methods implemented by this class

def sibling(self, p):

"""Return a position representing p's sibling (or None if no sibling)"""

parent = self.parent(p)

if parent is None:

return None

else:

if p == self.left(parent):

return self.right(parent)

else:

return self.left(parent)

def children(self, p):

"""Generate an iteration of Positions representing p's children"""

if self.left(p) is not None:

yield self.left(p)

if self.right(p) is not None:

yield self.right(p)

# -------------- traversal methods --------------------------------

def inorder(self):

"""Generate an inorder iteration of positions in the tree"""

if not self.is_empty():

for p in self._subtree_inorder(self.root()):

yield p

def _subtree_inorder(self, p):

if self.left(p) is not None: # If left child exists, traverse its subtree

for other in self._subtree_inorder(self.left(p)):

yield other

yield p

if self.right(p) is not None: # If right child exists, traverse its subtree

for other in self._subtree_inorder(self.right(p)):

yield other

# ------------ methods for saving to files ----------------------

def save_tree(self, filename):

"""Saves this tree to the specified filename in binary format.

Returns True if saved successfully, False if an error caused failure.

"""

try:

file = open(filename, 'wb')

pickle.dump(self, file)

file.close()

return True

except Exception:

return False

@staticmethod

def load_tree(filename):

"""Loads and returns a tree from the specified binary file."""

file = open(filename, 'rb')

data = pickle.load(file)

file.close()

return data

linked_binary_tree.py code

from binary_tree import BinaryTree

class Node:

__slots__ = '_element', '_parent', '_left', '_right'

def __init__(self, element, parent=None, left=None, right=None):

self._element = element

self._parent = parent

self._left = left

self._right = right

class Position(BinaryTree.Position):

"""An abstraction repreesnting the location of a single element."""

def __init__(self, container, node):

"""Constructor should not be invoked by user."""

self._container = container

self._node = node

def element(self):

"""Return the element stored at this position"""

return self._node._element

def __eq__(self, other):

"""Return True if other is a Position representing the same location"""

return type(other) is type(self) and other._node is self._node

class LinkedBinaryTree(BinaryTree):

"""Linked representation of a binary tree structure"""

def _validate(self, p):

"""Return associated node, if position is valid"""

if not isinstance(p, Position):

raise TypeError('p must be proper Position type')

if p._container is not self:

raise ValueError('p does not belong to this container')

if p._node._parent is p._node:

raise ValueError('p is no longer valid')

return p._node

def _make_position(self, node):

"""Return Position instance for given node (or None if no node)"""

if node is not None:

return Position(self, node)

return None

#----------------------constructor------------------------

def __init__(self):

"""Create an initially empty binary tree"""

self._root = None

self._size = 0

#------------------public accessors ------------------------

def __len__(self):

"""Return the total number of elements in the tree"""

return self._size

def root(self):

"""Return the root Position of the tree (or None if tree is empty)"""

return self._make_position(self._root)

def parent(self, p):

"""Return the Position of p's parent (or None if p is root)"""

node = self._validate(p)

return self._make_position(node._parent)

def left(self, p):

"""Return the Position of p's left child (or None if p has no left child)"""

node = self._validate(p)

return self._make_position(node._left)

def right(self, p):

"""Return the Position of p's right child (or None if p has no right child)"""

node = self._validate(p)

return self._make_position(node._right)

def num_children(self, p):

"""Return the number of children of Position p"""

node = self._validate(p)

count = 0

if node._left is not None:

count += 1

if node._right is not None:

count += 1

return count

# ------------------ non-public methods -----------------------

def _add_root(self, e):

"""Place element e at the root of an empty tree and return new Position.

Raise ValueError if tree nonempty.

"""

if self._root is not None:

raise ValueError('Root already exists')

self._size = 1

self._root = Node(e)

return self._make_position(self._root)

def _add_left(self, p, e):

"""Create a new left child for Position p, storing element e.

Return the Position of new node.

Raise ValueError if Position p is invalid or p already has a left child.

"""

node = self._validate(p)

if node._left is not None:

raise ValueError('Left child already exists')

self._size += 1

node._left = Node(e, node)

return self._make_position(node._left)

def _add_right(self, p, e):

"""Create a new right child for Position p, storing element e.

Return the Position of new node.

Raise ValueError if Position p is invalid or p already has a right child.

"""

node = self._validate(p)

if node._right is not None:

raise ValueError('Right child already exists')

self._size += 1

node._right = Node(e, node)

return self._make_position(node._right)

def _replace(self, p, e):

"""Replace the element at position p with e, and return old element"""

node = self._validate(p)

old = node._element

node._element = e

return old

def _delete(self, p):

"""Delete the node at Position p, and replace it with its child, if any.

Return the element that had been stored at Position p.

Raise ValueError if Position p is invalid or p has two children.

"""

node = self._validate(p)

if self.num_children(p) == 2:

raise ValueError('p has two children')

child = node._left if node._left else node._right

if child is not None:

child._parent = node._parent

if node is self._root:

self._root = child

else:

parent = node._parent

if node is parent._left:

parent._left = child

else:

parent._right = child

self._size -= 1

node._parent = node # Convention for deprecated node

return node._element

def _attach(self, p, t1, t2):

"""Attach trees t1 and t2 as left and right subtrees of external p"""

node = self._validate(p)

if not self.is_leaf(p):

raise ValueError('Position must be leaf')

if not type(self) is type(t1) is type(t2):

raise TypeError('Tree types must match')

self._size += len(t1) + len(t2)

if not t1.is_empty():

t1._root._parent = node

node._left = t1._root

t1._root = None

t1._size = 0

if not t2.is_empty():

t2._root._parent = node

node._right = t2._root

t2._root = None

t2._size = 0