There are two parts to this exercise. For each part, there is a single file you must submit — make sure that you read the submission instructions carefully!
BEFORE you begin coding, make sure that you understand everything in this handout. Remember that the point of these exercises is not to get a "working" program by any means necessary — it is to ensure that you understand how to write the desired code. If you succeed in writing something that works but you do not understand why, then you have failed, no matter what grade you receive!
In particular, if there is something you do not quite understand, please, for your own sake, take the time to read the online textbook and the course notes and readings, do some searching on Google and ask on the course forum or during office hours to make sure you find out.
Both parts of this exercise concern binary trees.
You have to write two methods — one each in Part A and Part B — to add to the following node class (available for download from the course website so that you don't have to copy-and-paste it from this handout).
class BTNode(object):
"""A node in a binary tree."""
def __init__(self, item, left=None, right=None):
"""(BTNode, object, BTNode, BTNode) -> NoneType
Initialize this node to store item and have children left and right,
as well as depth 0.
"""
self.item = item
self.left = left
self.right = right
self.depth = 0 # the depth of this node in a tree
def __str__(self):
"""(BTNode) -> str
Return a "sideways" representation of the subtree rooted at this node,
with right subtrees above parents above left subtrees and each node on
its own line, preceded by as many TAB characters as the node's depth.
"""
# If there is a right subtree, add an extra TAB character in front of
# every node in its string representation, with an extra newline at the
# end (ready to be concatenated with self.item).
if self.right:
str_right = "\t" + str(self.right).replace("\n", "\n\t") + "\n"
else:
str_right = ""
# The string representation of self.item: if item is a string, use
# repr(item) so that quotes are included and special characters are
# treated correctly -- just like in a list; else use str(item).
if isinstance(self.item, str):
str_item = repr(self.item)
else:
str_item = str(self.item)
# If there is a left subtree, add an extra TAB character in front of
# every node in its string representation, with an extra newline at the
# beginning (ready to be concatenated with self.item).
if self.left:
str_left = "\n\t" + str(self.left).replace("\n", "\n\t")
else:
str_left = ""
# Put the right subtree above the root above the left subtree.
return str_right + str_item + str_left
Copy the code for class BTNode into a new file named
"e5a.py" and add the following method to the
class — this includes writing the body of the method!
You must not change the constructor for class
BTNode, but you are allowed to add additional helper
methods if you think they are necessary. However, note that there is a way to
do this with no helper in about half a dozen lines: if your code is much
longer, there is a chance that you are missing something. Think about it
carefully to see if you can simplify.
def set_depth(self, depth):
"""(BTNode, int) -> NoneType
Set the .depth attribute of every node in the subtree rooted at this
node, starting with this node at depth 'depth'.
"""
Hint: First, draw a few simple trees and make sure that you understand what the correct result should be. Then, remember to think recursively!
Copy the code for class BTNode into a new file named
"e5b.py" and add the following method to the
class — this includes writing the body of the method!
You must not change the constructor for class
BTNode, but you are allowed to add additional helper
methods if you think they are necessary. However, note that there is a way to
do this with no helper in about a dozen lines: if your code is much longer,
there is a chance that you are missing something. Think about it carefully to
see if you can simplify.
def leaves_and_internals(self):
"""(BTNode) -> ([object], [object])
Return a pair of lists: (list of all the items stored in the leaves of
the subtree rooted at this node, list of all the items stored in the
internal nodes of the subtree rooted at this node).
"""
Hint: First, draw a few simple trees and make sure that you understand what the correct output should be. Then, remember to think recursively!