Python 3.x Binary Trees ADT This is ADT so remember to import Treenode.py This i

Question

Python 3.x Binary Trees ADT This is ADT so remember to import Treenode.py

This is what I have so far:

Treenode.py:

# Defines the tree node ADT

#
# A treenode is a simple container with three pieces of information
#   data: the contained information
#   left: a reference to another treenode or None
#   right: a reference to another treenode or None

# Implementation notes:
#   This implementation uses a Python dictionary as a record.

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 4 (8 points): Purpose: To do more thinking about binary trees. Degree of Difficulty: Tricky Tricky Tricky 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

Explanation / Answer

# below function can be called just with root nodes, and min and max # values will be empty at start, but slowly, they will be filled # based on root node data def ordered(tnode, minValue=None, maxValue=None): # a blank tre is always ordered if not tnode: return True # get the data of root node data = get_data(tnode) # if root data is in permissible limits if (minValue and data maxValue) : return False else: # to declare the whole tree as ordered, the left and right treees # should be ordered. # note: in next iterations, the value for min and max will # change as per the root node data leftOrdered = ordered(get_left(tnode), minValue, data-1) rightOrdered = ordered(get_right(tnode), data+1, maxValue) return leftOrdered and rightOrdered

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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