This is the Question

traversals.py

import treenode as tn import queue as Queue

def in_order(tnode): """ Display the nodes of a tree in pre-order. :param tnode: a primitive tree :return: nothing """ if tnode is None: return else: in_order(tn.get_left(tnode)) print(tn.get_data(tnode), end=" ") in_order(tn.get_right(tnode))

def pre_order(tnode): """ Display the nodes of a tree in pre-order. :param tnode: a primitive tree :return: nothing """ if tnode is None: return else: print(tn.get_data(tnode), end=" ") pre_order(tn.get_left(tnode)) pre_order(tn.get_right(tnode))

def post_order(tnode): """ Display the nodes of a tree in pre-order. :param tnode: a primitive tree :return: nothing """ if tnode is None: return else: post_order(tn.get_left(tnode)) post_order(tn.get_right(tnode)) print(tn.get_data(tnode), end=" ")

def breadth_first_order(tnode): """ Display the nodes of a tree in breadth-first-order. :param tnode: a primitive tree :return: nothing """ nodes = Queue.create() Queue.enqueue(nodes, tnode) order = Queue.create() # while Queue.size(nodes) > 0: current = Queue.dequeue(nodes) if current is not None: Queue.enqueue(order, tn.get_data(current)) Queue.enqueue(nodes, tn.get_left(current)) Queue.enqueue(nodes, tn.get_right(current))

while not Queue.is_empty(order): n = Queue.dequeue(order) print(n, end=" ")

treenode.py

def create(data, left=None, right=None): """ Create a new treenode for the given data. Pre-conditions: data: Any data value to be stored in the treenode left: Another treenode (or None, by default) Post-condition: none Return: the treenode created """ return {'data':data, 'left':left, 'right':right}

def get_data(treenode): """ Retrieve the contents of the data field. Pre-conditions: node: a node created by create() Post-conditions: none Return the data value stored previously in the node """ return treenode['data']

def get_left(tnode): """ Retrieve the contents of the left field. Pre-conditions: tnode: a treenode created by create() Post-conditions: none Return the value stored in left field """ return tnode['left']

def get_right(tnode): """ Retrieve the contents of the right field. Pre-conditions: tnode: a treenode created by create() Post-conditions: none Return the value stored in right field """ return tnode['right']

def set_data(tnode, val): """ Set the contents of the data field to val. Pre-conditions: tnode: a node created by create() val: a data value to be stored Post-conditions: stores the new data value, replacing the existing value Return none """ tnode['data'] = val

def set_left(tnode, val): """ Set the contents of left field to val. Pre-conditions: tnode: a treenode created by create() val: a treenode, or the value None Post-conditions: stores the val in left field, replacing the existing value Return none """ tnode['left'] = val

def set_right(tnode, val): """ Set the contents of right field to val. Pre-conditions: tnode: a treenode created by create() val: a treenode, or the value None Post-conditions: stores the val in right field, replacing the existing value Return none """ tnode['right'] = val

Question 3 (8 points): Purpose: To do more thinking about binary trees; to practice the art of internal functions; to practice the Degree of Difficulty: Moderate Write a function complete (tnode) that returns True is the given tree is a complete binary tree, and False art of tupling otherwise In class we defined a complete binary tree as follows: A complete binary tree is a binary tree that has exactly two children for every node, except for nodes at the maximum level, where the nodes are barren (i.e., leaf nodes) Visually, complete binary trees are easy to detect. But if you're just given a root node, it will be harder Consider the function below: 1def bad_complete (tnode): 2 3 4 def cmplt (tnode): if tnode is None: return else: 6 7 8 9 10 ldepth-cmplt (tn.get_left (tnode)) rdepth -cmplt (tn.get_right (tnode)) if ldepthrdepth: return rdepth+1 else: return -1 12 13 resultcmplt (tnode) return result> 0 Notice the internal definition of cmplt). This function is almost identical to our height function except for lines 8-11. The function uses the integer value -1 to report an incomplete tree. Whether this use of the return value is good or bad is a matter of opinion, but without an alternative, we make a virtue of necessity which is not always good! Rewrite the internal definition to return a tuple of 2 values, flag, height, where flag is True if the subtree is complete, False otherwise height is the height of the subtree, if flag is True, None otherwise This technique is called "tupling." You'll also have to change the second-to-last Line of the function, line 12 to account for the change to the internal function. Hint: Your internal function will return a tuple with 2 values. Python allows tuple assignment, i.e., an as- signment statement where tuples of the same length appear on both sides of the -. For example # tuple assignment a,b - 3,5 # tuple assignment a,b - b, a Question 3 (8 points): Purpose: To do more thinking about binary trees; to practice the art of internal functions; to practice the Degree of Difficulty: Moderate Write a function complete (tnode) that returns True is the given tree is a complete binary tree, and False art of tupling otherwise In class we defined a complete binary tree as follows: A complete binary tree is a binary tree that has exactly two children for every node, except for nodes at the maximum level, where the nodes are barren (i.e., leaf nodes) Visually, complete binary trees are easy to detect. But if you're just given a root node, it will be harder Consider the function below: 1def bad_complete (tnode): 2 3 4 def cmplt (tnode): if tnode is None: return else: 6 7 8 9 10 ldepth-cmplt (tn.get_left (tnode)) rdepth -cmplt (tn.get_right (tnode)) if ldepthrdepth: return rdepth+1 else: return -1 12 13 resultcmplt (tnode) return result> 0 Notice the internal definition of cmplt). This function is almost identical to our height function except for lines 8-11. The function uses the integer value -1 to report an incomplete tree. Whether this use of the return value is good or bad is a matter of opinion, but without an alternative, we make a virtue of necessity which is not always good! Rewrite the internal definition to return a tuple of 2 values, flag, height, where flag is True if the subtree is complete, False otherwise height is the height of the subtree, if flag is True, None otherwise This technique is called "tupling." You'll also have to change the second-to-last Line of the function, line 12 to account for the change to the internal function. Hint: Your internal function will return a tuple with 2 values. Python allows tuple assignment, i.e., an as- signment statement where tuples of the same length appear on both sides of the -. For example # tuple assignment a,b - 3,5 # tuple assignment a,b - b, a