''' Homework 4
-- Due Sunday, October 2nd at 23:59
-- Before starting, read
https://www.cis.upenn.edu/~cis192/homework/
-- Always write the final code yourself
-- Cite any websites you referenced
-- Use the PEP-8 checker for full style points:
https://pypi.python.org/pypi/pep8
'''
def gcd(a, b):
''' A gcd function for use below.'''
if b == 0:
return a
else:
return gcd(b, a % b)
class Rational(object):
''' Implement a rational numbers class. Include the following
magic methods: init, str, repr, add, sub, mul, truediv, and
lt, gt, ge, le, ne, eq.
Also include a from_string class method, that creates a Rational
from a string of the form "a/b".
Some notes:
-- Numeric operations should return a new Rational Object
-- All numbers should be in lowest terms at all times.
-- Denominators should never be negative (e.g. 2/-3 should be
written as (-2/3))
-- If the denominator is 1, only print the numerator.
-- use functools.total_ordering to supply the comparison methods
https://docs.python.org/3/library/functools.html
'''
pass
class BSTree(object):
''' Implement a binary search tree.
See here: http://en.wikipedia.org/wiki/Binary_search_tree
The examples in the test file illustrate the desired behavior.
Each method you need to implement has its own docstring
with further instruction. You'll want to move most of the
implementation details to the Node class below.
Additionally, keep count of the total number of Trees created
and the number of Nodes in each tree. Include a class method,
"num_trees" to return the former.
'''
def __init__(self):
pass
def __str__(self):
''' Return a representation of the tree as (left, elem, right)
where elem is the element stored in the root, and left and right
are the left and right subtrees (which print out similarly).
Empty trees should be represented by underscores.
'''
pass
def __len__(self):
''' Returns the number of nodes in the tree.'''
pass
def __contains__(self, element):
''' Finds whether a given element is in the tree.
Returns True if the element is found, else returns False.
'''
def insert(self, element):
''' Insert a given value into the tree.
Our implementation will allow duplicate nodes. The left subtree
should contain all elements <= to the current element, and the
right subtree will contain all elements > the current element.
'''
pass
def elements(self):
''' Return a list of the elements visited in an inorder traversal:
http://en.wikipedia.org/wiki/Tree_traversal
Note that this should be the sorted order if you've inserted all
elements using your previously defined insert function.
'''
pass
class Node(object):
''' A Node of the BSTree.
Important data attributes: value (or element), left and right.
'''
pass
def main():
pass
if __name__ == "__main__":
main()