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

You can find the treenode ADT on the assignment page. Using this ADT, implement the following functions: 1 subst (tnode, t, r) Purpose: To substitute a target value t with a replacement value r wherever it 2. copy (tnode) Purpose: To create an exact copy of the given tree, with completely new treenodes, but appears in the given tree. Returns None, but modifies the given tree exactly the same data values, in exactly the same places. If tnode is None, return None. If tnode is not None, return a reference to the new tree 3. collect_data_inorder (tnode) Purpose: To collect all the data values in the given tree. Returns a list of all the data values, and the data values appear in the list according to the in-order sequence. Hint: count_smaller (tnode, target) Purpose: Count the number of data values in the given tree that are On Moodle you will find a file called exampletrees.py which has a few example trees that you can use for Base this function on the in_order ) traversal, which you can find in traversals.py less than the given target value. Assume that the given tree has data values that are number only demonstration and testing. This file also recommends a demonstration strategy for each function. You'll also find some useful functions in the file treefunctions.py Note: Test your functions carefully. You may start with the trees in the Python file provided, but those are demonstrations. Your testing could and probably should be a bit more deliberate You can find the treenode ADT on the assignment page. Using this ADT, implement the following functions: 1 subst (tnode, t, r) Purpose: To substitute a target value t with a replacement value r wherever it 2. copy (tnode) Purpose: To create an exact copy of the given tree, with completely new treenodes, but appears in the given tree. Returns None, but modifies the given tree exactly the same data values, in exactly the same places. If tnode is None, return None. If tnode is not None, return a reference to the new tree 3. collect_data_inorder (tnode) Purpose: To collect all the data values in the given tree. Returns a list of all the data values, and the data values appear in the list according to the in-order sequence. Hint: count_smaller (tnode, target) Purpose: Count the number of data values in the given tree that are On Moodle you will find a file called exampletrees.py which has a few example trees that you can use for Base this function on the in_order ) traversal, which you can find in traversals.py less than the given target value. Assume that the given tree has data values that are number only demonstration and testing. This file also recommends a demonstration strategy for each function. You'll also find some useful functions in the file treefunctions.py Note: Test your functions carefully. You may start with the trees in the Python file provided, but those are demonstrations. Your testing could and probably should be a bit more deliberate