Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

Lab 5 ● Declare and implement a BSTNode ADT with a data attribute and two pointer attributes, one for the left child and the other for the right child. Implement the usual getters/setters for these...

2 answer below »
Lab 5
● Declare and implement a BSTNode ADT with a data attribute and two pointe
attributes, one for the left child and the other for the right child. Implement the
usual getters/setters for these attributes.
● Declare and implement a BST as a link-based ADT whose data will be Money
objects - the data will be inserted based on the actual money value of you
MOney objects as a combination of the whole value and fractional value
attributes.
● For the BST, implement the four traversal methods as well as methods for the
usual search, insert, delete, print, count, isEmpty, empty operations and any
other needed.
● Your pgm will use the following 20 Money (think of them in Dollar terms)
objects to be created in the exact order in your main to seed the tree:
1. $57.12
2. $23.44
3. $87.43
4. $68.99
5. $111.22
6. $44.55
7. $77.77
8. $18.36
9. $543.21
10.$20.21
11. $345.67
12.$36.18
13.$48.48
14.$101.00
15.$11.00
16.$21.00
17.$51.00
18.$1.00
19.$251.00
20.$151.00
● Also, create an output file to write program output as specified in one o
more instructions below.
● After seeding the data, perform your traversal operations in the specific
sequence of
eadth-first, in-order, pre-order, post-order, ensuring that output
is written out to both screen and file concu
ently.
● Then provide interactivity for the user to add/search/delete nodes from the
console after the data has been seeded into the application.
● Perform adequate input data validation when reading data from the user into
the tree - if any data item is invalid, ignore the data item and continue to next
item but print a message to output (both screen and same output file) to
indicate which data items were ignored.
● Also, provide the user the option to print output of traversals or exit the
program. Once the user selects the option to print data or exits the program,
the data in the BST should be printed out to both screen and output file in all
four traversal methods in the specific sequence of
eadth-first, in-order,
pre-order, post-order.
● demonstrate use of your Lab 4 queue without any modifications for the
tree traversals

Lab 4 Tannaz Anvari/IDE Test #1.jpg
Lab 4 Tannaz Anvari/IDE Test #2.jpg
Lab 4 Tannaz Anvari/linkedlist.py
"""
CIS 22C Summer Quarte
Professor: Manish Goel
Student: Tannaz Anvari
**********
Lab 4
Started date: 7/21/2021
Final submission date: 07/26/2021
"""
"""
A Singly Linked List class which will be composed of three attributes - a count attribute, a LinkedNode
pointe
eference attribute pointing to the start of the list and a LinkedNode pointe
eference attribute pointing
to the end of the list. Since this is a class, make sure all these attributes are private
"""
# LinkedNode Class Starts
class LinkedNode:
# Constructo
def __init__(self, data):
XXXXXXXXXXself.data = data
XXXXXXXXXXself.next = None
# Getters
def get_data(self):
XXXXXXXXXXreturn self.data
def get_next(self):
XXXXXXXXXXreturn self.next
# Setters
def set_data(self, data):
XXXXXXXXXXself.data = data
def set_next(self, next):
XXXXXXXXXXself.next = next
XXXXXXXXXXdef __str__(self):
XXXXXXXXXXreturn str(self.data)
# LinkedNode Class Ends
# SinglyLinkedList Class Starts
class SinglyLinkedList:
# Constructo
def __init__(self):
XXXXXXXXXXself.count = 0
XXXXXXXXXXself.start = self.end = None
# Getters
def get_count(self):
XXXXXXXXXXreturn self.count
def get_start(self):
XXXXXXXXXXreturn self.start
def get_end(self):
XXXXXXXXXXreturn self.end
# Setters
def set_count(self, count):
XXXXXXXXXXself.count = count
def set_start(self, start):
XXXXXXXXXXself.start = start
def set_end(self, end):
XXXXXXXXXXself.end = end
# Other methods
def add_to_front(self, data):
XXXXXXXXXXnode = LinkedNode(data)
XXXXXXXXXXif self.count == 0: # List is empty
XXXXXXXXXXself.start = node
XXXXXXXXXXself.end = node
XXXXXXXXXXelse: # List is not empty
XXXXXXXXXXnode.set_next(self.start)
XXXXXXXXXXself.start = node
XXXXXXXXXXself.count += 1
def add_to_end(self, data):
XXXXXXXXXXnode = LinkedNode(data)
XXXXXXXXXXif self.count == 0: # List is empty
XXXXXXXXXXself.start = node
XXXXXXXXXXself.end = node
XXXXXXXXXXelse:
XXXXXXXXXXself.end.set_next(node)
XXXXXXXXXXself.end = node
XXXXXXXXXXself.count += 1
def get_front_data(self):
XXXXXXXXXXif self.count == 0:
XXXXXXXXXXreturn None
XXXXXXXXXXreturn self.start.get_data()
def get_end_data(self):
XXXXXXXXXXif self.count == 0:
XXXXXXXXXXreturn None
XXXXXXXXXXreturn self.end.get_data()
def is_empty(self):
XXXXXXXXXXreturn self.count == 0
def delete_from_front(self):
XXXXXXXXXXif self.count == 0:
XXXXXXXXXXreturn
XXXXXXXXXXelif self.count == 1:
XXXXXXXXXXself.start = self.end = None
XXXXXXXXXXelse:
XXXXXXXXXXself.start = self.start.get_next()
XXXXXXXXXXself.count -= 1
def find_data(self, data):
XXXXXXXXXXcu
= self.start
XXXXXXXXXXwhile cu
is not None:
XXXXXXXXXXd = cu
.get_data()
XXXXXXXXXXif d == data:
XXXXXXXXXXreturn True
XXXXXXXXXXcu
= cu
.get_next()
XXXXXXXXXXreturn False
def __str__(self):
XXXXXXXXXXcu
= self.start
# The attribute names for the Node and Linked List are the words in bold in #1 and #2
XXXXXXXXXXs = "SLL with " + str(self.count) + " nodes: "
XXXXXXXXXXwhile cu
is not None:
XXXXXXXXXXd = cu
.get_data()
XXXXXXXXXXs = s + str(d) + " -> "
XXXXXXXXXXcu
= cu
.get_next()
XXXXXXXXXXreturn s
# SinglyLinkedList Class Ends
Lab 4 Tannaz Anvari/main.py
"""
CIS 22C Summer Quarte
Professor: Manish Goel
Student: Tannaz Anvari
**********
Lab 4
Started date: 7/21/2021
Final submission date: 07/26/2021
"""
# importing files
import linkedlist as LL
import queue as Q
import stack as S
import money as M
import random
# main function definition
def main():
LinkedList_tests()
Stack_tests()
Queue_tests()
# definition of all the test methods
def create_test_data():
data = []
# Create seven (7) Node objects of Money class to be used in the program.
for i in range(7):
XXXXXXXXXXamount = random.randint(1, 100)
XXXXXXXXXXm = M.Money(amount)
XXXXXXXXXXdata.append(m)
return data
def LinkedList_tests():
File = open('outcome.txt', 'a')
print("Linked List tests")
File.write("Linked List tests\n")
data = create_test_data()
L = LL.SinglyLinkedList()
L.add_to_front(data[0])
print(str(L))
File.write(str(L)+'\n')
L.add_to_front(data[1])
print(str(L))
File.write(str(L)+'\n')
L.add_to_end(data[2])
print(str(L))
File.write(str(L)+'\n')
print("The number at the front of the list: " + str(L.get_front_data()))
File.write("The number at the front of the list: " + str(L.get_front_data())+'\n')
print("The number at the end of the list: " + str(L.get_end_data()))
File.write("The number at the end of the list: " + str(L.get_end_data())+'\n')
L.delete_from_front()
print(str(L))
File.write(str(L)+'\n')
L.add_to_end(data[3])
print(str(L))
File.write(str(L)+'\n')
print("count = " + str(L.get_count()))
File.write("count = " + str(L.get_count())+'\n')
print("_" * 50)
File.write(("_" * 50)+'\n')
File.close()
def Stack_tests():
File = open('outcome.txt', 'a')
print("Stack tests")
File.write("Stack tests\n")
s
lab-5-0butl5xm.pdf lab-4-tannaz-anvari-xbum4c1x.zip
Answered 4 days After Jul 29, 2021

Solution

Sandeep Kumar answered on Aug 03 2021
155 Votes
binary_tree.py
# Copyright 2013, Michael H. Goldwasse
#
# Developed for use with the book:
#
# Data Structures and Algorithms in Python
# Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasse
# John Wiley & Sons, 2013
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, o
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied wa
anty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see www.gnu.org/licenses
.
from tree import Tree
class BinaryTree(Tree):
"""Abstract base class representing a binary tree structure."""
# --------------------- additional abstract methods ---------------------
def left(self, p):
"""Return a Position representing p's left child.
Return None if p does not have a left child.
"""
raise NotImplementedE
or('must be implemented by subclass')
def right(self, p):
"""Return a Position representing p's right child.
Return None if p does not have a right child.
"""
raise NotImplementedE
or('must be implemented by subclass')
# ---------- concrete methods implemented in this class ----------
def sibling(self, p):
"""Return a Position representing p's sibling (or None if no sibling)."""
parent = self.parent(p)
if parent is None: # p must be the root
return None # root has no sibling
else:
if p == self.left(parent):
return self.right(parent) # possibly None
else:
return self.left(parent) # possibly None
def children(self, p):
"""Generate an iteration of Positions representing p's children."""
if self.left(p) is not None:
yield self.left(p)
if self.right(p) is not None:
yield self.right(p)
def inorder(self):
"""Generate an inorder iteration of positions in the tree."""
if not self.is_empty():
for p in self._subtree_inorder(self.root()):
yield p
def _subtree_inorder(self, p):
"""Generate an inorder iteration of positions in subtree rooted at p."""
if self.left(p) is not None: # if left child exists, traverse its subtree
for other in self._subtree_inorder(self.left(p)):
yield othe
yield p # visit p between its subtrees
if self.right(p) is not None: # if right child exists, traverse its subtree
for other in self._subtree_inorder(self.right(p)):
yield othe
# ove
ide inherited version to make inorder the default
def positions(self):
"""Generate an iteration of the tree's positions."""
return self.inorder() # make inorder the default
extended_linked_binary_tree.py
from linked_binary_tree import LinkedBinaryTree
from linked_queue import Empty
class ExtendedBinaryTree(LinkedBinaryTree):
def __init__(self):
super().__init__()
def preorder_next(self, p):
'''Return the position visited after p in a preorder traversal of T (or None if p is the
last node visited)
'''
if self.is_empty(): # Raise exception if the tree is empty.
raise Empty("Tree is empty")
cu
ent_node = p # Otherwise, set the given position to cu
ent_node.
if self.left(cu
ent_node) is not None: # If the cu
ent_node has a left child, return it.
return self.left(cu
ent_node)
elif self.right(cu
ent_node) is not None: # If the cu
ent_node has a right child, return it.
return self.right(cu
ent_node)
else:
parent_node = self.parent(cu
ent_node) # Set parent_node to the parent of the cu
ent node.
if self.left(parent_node) == cu
ent_node and self.sibling(
cu
ent_node): # If the cu
ent_node is a left child and has a sibling, return its sibling.
return self.right(parent_node)
elif self.num_children(cu
ent_node) == 0 and self.right(parent_node) == cu
ent_node or self.left(
parent_node) == cu
ent_node: # Else if the cu
ent node is right child (leaf) of the parent node, or a left child
if parent_node == self.right(
self.parent(parent_node)): # If the parent_node is the right child of its parent
parent_node = self.parent(parent_node) # Set the parent_node to parent_node's parent.
if self.parent(parent_node) == None: # Return 'None' if it's the alst node visited.
return None
return self.right(self.parent(parent_node)) # Return the right child of parent_node's parent.
def inorder_next(self, p):
'''Return the position visited after p in an inorder traversal of T (or None if p is the
last node visited).
'''
if self.is_empty(): # Check if the tree is empty.
raise Empty("Tree is empty")
else:
cu
ent_node = p # If the tree isn't empty, set cu
ent_node to p, and cu
ent_node's right child to right.
right = self.right(cu
ent_node)
if (right != None) and self.num_children(
right) == 0: # If the right child exists, and has no children, return it.
return right
elif right and self.left(
right): # If the right child exists, and has a left child, set the cu
ent_node to the right child.
cu
ent_node = right
while self.left(
cu
ent_node): # As long as the cu
ent_node has a left child, set the cu
ent node to it's left child.
cu
ent_node = self.left(cu
ent_node)
return cu
ent_node # If cu
ent_node does not have a left child, return it.
elif (self.left(cu
ent_node) == None and right == None) or (self.left(
cu
ent_node) and right == None): # If the cu
ent node has no children, or only has a left child, set the cu
ent node to it's parent.
cu
ent_node = self.parent(cu
ent_node)
if self.left(cu
ent_node) == p: # If the left child of the cu
ent node is P, return it.
return cu
ent_node
else:
while cu
ent_node == self.right(
self.parent(cu
ent_node)): # Otherwise, look for it's parent, and return it.
cu
ent_node = self.parent(cu
ent_node)
if self.parent(cu
ent_node) == None: # Return None if it's the last node visited.
return None
return self.parent(cu
ent_node)
def postorder_next(self, p):
'''Return the position visited after p in a postorder traversal of T (or None if p is
the last node visited)
'''
if self.is_empty(): # Check if the tree is empty. If it is, raise an exception.
raise Empty("Tree is empty!")
else:
cu
ent_node = p # Otherwise set the cu
ent_node to p.
if self.is_root(cu
ent_node): # If the cu
ent_node is the root (last node visited), return 'None'.
return None
if self.sibling(cu
ent_node) is None: # If the cu
ent_node has no sibling, return its parent.
return self.parent(cu
ent_node)
elif self.sibling(
cu
ent_node): # Otherwise, if it has a sibling, set parent_node to the parent of cu
ent_node.
parent_node = self.parent(cu
ent_node)
if self.left(
parent_node) == cu
ent_node: # If the cu
ent_node is the left child, and cu
ent_node's sibling is a leaf, return the sibling.
if self.num_children(self.right(parent_node)) == 0:
return self.right(parent_node)
else: # Otherwise, set parent node to the right child of parent_node.
parent_node = self.right(parent_node)
while self.num_children(
parent_node) > 0: # As long as parent_node has children, if it has a left child, set parent_node to the left child.
if self.left(parent_node):
parent_node = self.left(parent_node)
else:
parent_node = self.right(parent_node) # Otherwise set it to the right child.
return parent_node # Then return it.
elif self.right(
parent_node) == cu
ent_node: # If the cu
ent_node is its parent's right child, return the parent.
return parent_node
def delete_subtree(self, p):
'''Remove the entire subtree rooted at position p, making sure to maintain the
count on the size of the tree.
'''
if self.is_empty():
raise Empty("Queue is empty") # Check if the tree is empty. If it is, raise an exception.
else:
cu
ent_node = self._validate(p) # Validate p's position, and set it to cu
ent_node.
parent_node = cu
ent_node._parent # Set parent_node to cu
ent_node's parent.
if parent_node._left is cu
ent_node: # If cu
ent_node is a left child, delete the subtree.
parent_node._left = None
else:
parent_node._right = None # Else, if it's a right child, delete the subtree.
x = self._subtree_inorder(p) # Maintain the count on the size of the tree by using inorder traversal.
num_deleted = 0
for i in x:
num_deleted += 1
self._size -= num_deleted
return self._size
def tree_v1(self):
"""Creating 4 different types of test trees to cover all the possible cases"""
Q = ExtendedBinaryTree()
# Example of a improper binary tree
t_0 = Q._add_root(23)
t_1 = Q._add_left(t_0, 15)
t_2 = Q._add_right(t_0, 63)
t_3 = Q._add_left(t_1, 8)
t_4 = Q._add_right(t_1, 20)
t_5 = Q._add_left(t_2, 32)
t_6 = Q._add_right(t_2, 80)
t_7 = Q._add_left(t_4, 19)
t_8 = Q._add_right(t_4, 22)
t_9 = Q._add_right(t_5, 60)
t_10 = Q._add_left(t_9, 50)
return Q, t_0, t_1, t_2, t_3, t_4, t_5, t_6, t_7, t_8, t_9, t_10 # return Tree first and all the other nodes afterwards
def tree_v2(self):
P = ExtendedBinaryTree()
# Example of a improper binary tree with only left children
t_0 = P._add_root("A")
t_1 = P._add_left(t_0, 'B')
t_2 = P._add_left(t_1, 'C')
t_3 = P._add_left(t_2, 'D')
t_4 = P._add_left(t_3, 'E')
t_5 = P._add_left(t_4, 'F')
t_6 = P._add_left(t_5, 'G')
return P, t_0, t_1, t_2, t_3, t_4, t_5, t_6
def tree_v3(self):
T = ExtendedBinaryTree()
# Example of a binary tree with only a root
t_0 = T._add_root("Root")
return T, t_0
def tree_v4(self):
I = ExtendedBinaryTree()
# Example of a proper binary tree
t_0 = I._add_root(0)
t_1 = I._add_left(t_0, 1)
t_2 = I._add_right(t_0, 2)
t_3 = I._add_left(t_2, 5)
t_4 = I._add_right(t_2, 6)
t_5 = I._add_left(t_4,7)
t_6 = I._add_right(t_4,8)
return I, t_0, t_1, t_2, t_3, t_4, t_5, t_6
import unittest
class TestGroupProject(unittest.TestCase):
"""Unittest Class starts here"""
def test_preorder_tree1(self):
"""Check if preorder traversal is the same as preorder_next on every node for tree 1"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v1()[0]
positional_list = []
myList1 = [] # List will contain preorder traversal values
myList2 = [] # This one will contain preorder_next on every node
for i in Q.preorder():
positional_list.append(i)
for i in Q.preorder():
myList1.append(i.element())
myList2.append(positional_list[0].element()) # Add the very first node manually to keep all the elements
for e in positional_list[:-1]:
myList2.append(Q.preorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_preorder_tree2(self):
"""Check if preorder traversal is the same as preorder_next on every node for tree 2"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v2()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.preorder():
positional_list.append(i)
for i in Q.preorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.preorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_preorder_tree3(self):
"""Check if preorder traversal is the same as preorder_next on every node for tree 3"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v3()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.preorder():
positional_list.append(i)
for i in Q.preorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.preorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_preorder_tree4(self):
"""Check if preorder traversal is the same as preorder_next on every node for tree 4"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v4()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.preorder():
positional_list.append(i)
for i in Q.preorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.preorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_inorder_tree1(self):
"""Check if inorder traversal is the same as inorder_next on every node for tree 1"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v1()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.inorder():
positional_list.append(i)
for i in Q.inorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.inorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_inorder_tree2(self):
"""Check if inorder traversal is the same as inorder_next on every node for tree 2"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v2()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.inorder():
positional_list.append(i)
for i in Q.inorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.inorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_inorder_tree3(self):
"""Check if inorder traversal is the same as inorder_next on every node for tree 3"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v3()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.inorder():
positional_list.append(i)
for i in Q.inorder():
myList1.append(i.element())
myList2.append(positional_list[0].element())
for e in positional_list[:-1]:
myList2.append(Q.inorder_next(e).element())
self.assertEqual(myList1, myList2)
def test_inorder_tree4(self):
"""Check if inorder traversal is the same as inorder_next on every node for tree 4"""
Tree = ExtendedBinaryTree()
Q = Tree.tree_v4()[0]
positional_list = []
myList1 = []
myList2 = []
for i in Q.inorder():
positional_list.append(i)
for i in Q.inorder():
...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Attach File