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

We say that a binary tree is ordered if all of the following conditions are true: 1. The left subtree is ordered. 2. The right subtree is ordered. 3. If the left subtree is not empty. all of the data values in the left subtree are less than the data value at the root. 4. If the right subtree is not empty, all of the data values in the right subtree are greater than the data value at the root. The empty tree is ordered by definition Write a function ordered (tnode) that returns True if the given tree is ordered, and False otherwise. What to Hand In . A file called a8q4.py. containing your function definition. . A file called a8q4_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