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

Purpose: To do more thinking about binary trees. Degree of Difficulty: Moderate We say that two binary trees ti and t2 satisfy the mirror property if all of the following conditions are true 1. The data value stored in the root of ti is equal to the data value stored in the root of t2 2. The left subtree of ti and the right subtree of t2 satisfy the mirror property. 3. The right subtree of ti and the left subtree of t2 satisfy the mirror property. If both t1 and t2 are empty. we say the mirror property is satisfied, but if one is empty but the other is not. the mirror property is not satisfied Write a function mirrored(t1, t2) that returns True if the two given trees satisfy the mirror property. and False otherwise. What to Hand In . A file called a8q2.py, containing your function definition. .A file called a8q2 testing.py. containing your testing Be sure to include your name, NSID, student number, course number and laboratory section at the top of the file. Purpose: To do more thinking about binary trees. Degree of Difficulty: Moderate We say that two binary trees ti and t2 satisfy the mirror property if all of the following conditions are true 1. The data value stored in the root of ti is equal to the data value stored in the root of t2 2. The left subtree of ti and the right subtree of t2 satisfy the mirror property. 3. The right subtree of ti and the left subtree of t2 satisfy the mirror property. If both t1 and t2 are empty. we say the mirror property is satisfied, but if one is empty but the other is not. the mirror property is not satisfied Write a function mirrored(t1, t2) that returns True if the two given trees satisfy the mirror property. and False otherwise. What to Hand In . A file called a8q2.py, containing your function definition. .A file called a8q2 testing.py. containing your testing Be sure to include your name, NSID, student number, course number and laboratory section at the top of the file