traversals.py import treenode as tn import queue as Queue def in_order(tnode): \

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

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.

Explanation / Answer

For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

Note :Please look for the comments to understand the code

/* Returns true if a binary tree is ordered */

int isOrdered(struct node* node)

{

  if (node == NULL)

    return(true);

     

  /* false if the max of the left is > than us */

  if (node->left!=NULL && maxValue(node->left) > node->data)

    return(false);

     

  /* false if the min of the right is <= than us */

  if (node->right!=NULL && minValue(node->right) < node->data)

    return(false);

   

  /* false if, recursively, the left or right is not a Ordered tree*/

  if (!isOrdered(node->left) || !isOrdered(node->right))

    return(false);

     

  /* passing all that, it's a ordered tree*/

  return(true);

}

/* Returns true if a binary tree is ordered */

int isOrdered(struct node* node)

{

  if (node == NULL)

    return(true);

     

  /* false if the max of the left is > than us */

  if (node->left!=NULL && maxValue(node->left) > node->data)

    return(false);

     

  /* false if the min of the right is <= than us */

  if (node->right!=NULL && minValue(node->right) < node->data)

    return(false);

   

  /* false if, recursively, the left or right is not a Ordered tree*/

  if (!isOrdered(node->left) || !isOrdered(node->right))

    return(false);

     

  /* passing all that, it's a ordered tree*/

  return(true);

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.