QuestionQuestion

Binary Tree

Using the algorithm Saruman devised above, he is able to begin destroying the Ents as they attempt to destroy his tower. However, recognizing the Ent’s power, Saruman decides he needs a tree of his own. Help him create a data structure, a linked binary tree, to use the power of trees for evil.

Your assignment is to implement, in Python, the linked binary tree data struc- ture.
Remember that when doing object-oriented programming in Python, there’s an obligatory self argument for every function. But this is only when you’re defining the method signature! When you call the method, the parameter is implicit: you don’t need to pass it, Python handles it for you.

Requirements

Functionality
Fill in all of the methods in bintree.py. Make sure methods run as efficiently as possible. Remember that the height of an empty tree is undefined and the height of a one-node tree is zero. If the user calls the height() method when the height of the tree is undefined, you should throw an exception.

Note: Do not name variables the same name as a method declaration. You will get a TypeError saying that the “object is not callable.”

Runtime Requirements
Each of the methods you are writing should run in O(1) worst-case time. We have emphasized this in the stencil where it is quite possible to implement it otherwise.

Testing
As always, you will need to make and hand in your own test cases, but you knew that. You should write all of your test functions in the provided file bt_test.py. Don’t forget to comment each test so it’s clear what you’re testing for.

Stencil Code and Hints
As usual, we have provided you with stencil code. To succeed on this problem, and to make the most of our stencil, you may find it helpful to read through the following hints.

The stencil contains 4 classes:

1. EmptyBinTreeException: This class defines an exception that you should throw when methods are called on an empty binary tree. The docstrings provided in the stencil should indicate when this exception should be thrown.

2. InvalidInputException: This class defines an exception that you should throw when methods are called with invalid parameters. The docstrings provided in the stencil should indicate when this exception should be thrown.

3. Node: This class defines a Node. Your tree will contain many of these. You are responsible for filling out any method in this class marked with TODO. It is very important that you read the note below regarding the self-argument passed to each method in this class.

4. BinTree: This class defines the Linked Binary Tree data structure. You are responsible for filling out any method in this class marked with TODO. It is very important that you read the note below regarding the self-argument passed to each method in this class.

An important note about the self argument: Remember that when doing object-oriented programming in Python, there’s an obligatory self-argument for every function. This argument can be used to access the internal attributes of a particular class since these variables cannot be accessed directly. We do this from within a method by calling self.<attribute> (without the angle brackets). Also remember, however, that the self argument is only used when defining a method. When calling the method, Python passes this argument for you, and you should leave it out.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#! /usr/bin/python
# hashset.py

""" HashSet module

Implement a HashSet with an array/list as the underlying data structure

IMPORTANT: Do not use the python's built-in hash set functionality.
You will receive no credit if you use Python's sets
or dictionaries. You should only need to use Python lists.
"""
import string
import sys
import os
import random

class InvalidInputException(Exception):
    def __init__(self,value):
       self.value = value
    def __str__(self):
       return repr(self.value)

def smallest_prime(start):
    """
    Input: The starting number
    Output: The smallest prime >= start
    Purpose: Finds the smallest prime >= start and returns it.
    """
    while not is_prime(start):
       start += 1
    return start

def is_prime(num):
    """
    Input: num - The number to check for primality
    Output: True if num is prime, False otherwise.
    Purpose: Check if num is prime.
    """
    for divisor in range(2, int(num ** 0.5) + 1):
       if num % divisor == 0:
            return False
    return True


class HashSet:
    """ HashSet Class
    Implement a hash set with an array/list as the underlying data structure
    """

    def __init__(self, expected_size=256, key_length=3):
       """
       Input: self - hash set object
                expected_size - the size of the hash set, default is 256.
                      Note that even if expected_size is composite, the size of
                      the underlying data-structure should be prime.
                key_length - the length of keys for this hash set, default is 3.
       Output: Nothing...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

50% discount

Hours
Minutes
Seconds
$25.00 $12.50
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Python Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats