Question

"""Prep 7 Synthesize === CSC148 Fall 2020 === Department of Mathematical and Computational Sciences, University of Toronto Mississauga === Module Description === Your task in this prep is to implement each of the unimplemented Tree methods in this file. The starter code has a recursive template that includes the "size-one" case; you may or may not choose to use this in your final implementations. """ from __future__ import annotations from typing import Any, List, Optional class Tree: """A recursive tree data structure. Note the relationship between this class and RecursiveList; the only major difference is that _rest has been replaced by _subtrees to handle multiple recursive sub-parts. """ # === Private Attributes === # The item stored at this tree's root, or None if the tree is empty. _root: Optional[Any] # The list of all subtrees of this tree. _subtrees: List[Tree] # === Representation Invariants === # - If self._root is None then self._subtrees is an empty list. # This setting of attributes represents an empty Tree. # # Note: self._subtrees may be empty when self._root is not None. # This setting of attributes represents a tree consisting of just one # node. def __init__(self, root: Any, subtrees: List[Tree]) -> None: """Initialize a new Tree with the given root value and subtrees. If <root> is None, the tree is empty. Precondition: if <root> is None, then <subtrees> is empty. """ self._root = root self._subtrees = subtrees def is_empty(self) -> bool: """Return True if this tree is empty. >>> t1 = Tree(None, []) >>> t1.is_empty() True >>> t2 = Tree(3, []) >>> t2.is_empty() False """ return self._root is None def __len__(self) -> int: """Return the number of items contained in this tree. >>> t1 = Tree(None, []) >>> len(t1) 0 >>> t2 = Tree(3, [Tree(4, []), Tree(1, [])]) >>> len(t2) 3 """ if self.is_empty(): return 0 size = 1 # count the root for subtree in self._subtrees: size += subtree.__len__() # could also do len(subtree) here return size # TODO: implement this method! def num_positives(self) -> int: """Return the number of positive integers in this tree. Precondition: all items in this tree are integers. Remember, 0 is *not* positive. >>> t1 = Tree(17, []) >>> t1.num_positives() 1 >>> t2 = Tree(-10, []) >>> t2.num_positives() 0 >>> t3 = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])]) >>> t3.num_positives() 2 """ # if self.is_empty(): # ... # elif self._subtrees == []: # ... # else: # ... # for subtree in self._subtrees: # ... subtree.num_positives() ... # ... pass # TODO: implement this method! def maximum(self: Tree) -> int: """Return the maximum item stored in this tree. Return 0 if this tree is empty. Precondition: all values in this tree are positive integers. >>> t1 = Tree(17, []) >>> t1.maximum() 17 >>> t3 = Tree(1, [Tree(12, []), Tree(10, []), Tree(30, [])]) >>> t3.maximum() 30 """ # if self.is_empty(): # ... # elif self._subtrees == []: # ... # else: # ... # for subtree in self._subtrees: # ... subtree.maximum() ... # ... pass # TODO: implement this method! def height(self: Tree) -> int: """Return the height of this tree. Please refer to the prep readings for the definition of tree height. >>> t1 = Tree(17, []) >>> t1.height() 1 >>> t2 = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])]) >>> t2.height() 2 """ # if self.is_empty(): # ... # elif self._subtrees == []: # ... # else: # ... # for subtree in self._subtrees: # ... subtree.height() ... # ... pass # TODO: implement this method! def __contains__(self, item: Any) -> bool: """Return whether this tree contains <item>. >>> t = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])]) >>> t.__contains__(-30) # Could also write -30 in t. True >>> t.__contains__(148) False """ # if self.is_empty(): # ... # elif self._subtrees == []: # ... # else: # ... # for subtree in self._subtrees: # ... subtree.__contains__(...) ... # ... pass if __name__ == '__main__': import doctest doctest.testmod() import python_ta python_ta.check_all()

Answer #1

The following python program does all the required tasks with the required formatting. Output is also shown at the end to confirm. Read the comments in the code.

num_positives :- Check if the tree is empty. If it is, then return 0 because there cannot be any positives. Otherwise recursively call this on all subtrees of tree and add the result to ans.

maximum:- Store current root's value in ans. Find the maximum in all subtrees and return the final maximum

height:- Find maximum height of all subtrees and add 1 to this to include root to get the final height.

contains:- Check if root is equal to item. If it is, then return True as element is found. Otherwise, find the element in all subtrees.If it is found in one of the subtrees, return True. Otherwise return False.

```
"""Prep 7 Synthesize
=== CSC148 Fall 2020 ===
Department of Mathematical and Computational Sciences,
University of Toronto Mississauga
=== Module Description ===
Your task in this prep is to implement each of the unimplemented Tree methods
in this file.
The starter code has a recursive template that includes the "size-one" case;
you may or may not choose to use this in your final implementations.
"""
from __future__ import annotations
from typing import Any, List, Optional
class Tree:
"""A recursive tree data structure.
Note the relationship between this class and RecursiveList; the only major
difference is that _rest has been replaced by _subtrees to handle multiple
recursive sub-parts.
"""
# === Private Attributes ===
# The item stored at this tree's root, or None if the tree is empty.
_root: Optional[Any]
# The list of all subtrees of this tree.
_subtrees: List[Tree]
# === Representation Invariants ===
# - If self._root is None then self._subtrees is an empty list.
# This setting of attributes represents an empty Tree.
#
# Note: self._subtrees may be empty when self._root is not None.
# This setting of attributes represents a tree consisting of just one
# node.
def __init__(self, root: Any, subtrees: List[Tree]) -> None:
"""Initialize a new Tree with the given root value and subtrees.
If <root> is None, the tree is empty.
Precondition: if <root> is None, then <subtrees> is empty.
"""
self._root = root
self._subtrees = subtrees
def is_empty(self) -> bool:
"""Return True if this tree is empty.
>>> t1 = Tree(None, [])
>>> t1.is_empty()
True
>>> t2 = Tree(3, [])
>>> t2.is_empty()
False
"""
return self._root is None
def __len__(self) -> int:
"""Return the number of items contained in this tree.
>>> t1 = Tree(None, [])
>>> len(t1)
0
>>> t2 = Tree(3, [Tree(4, []), Tree(1, [])])
>>> len(t2)
3
"""
if self.is_empty():
return 0
size = 1 # count the root
for subtree in self._subtrees:
size += subtree.__len__() # could also do len(subtree) here
return size
def num_positives(self) -> int:
"""Return the number of positive integers in this tree.
Precondition: all items in this tree are integers.
Remember, 0 is *not* positive.
>>> t1 = Tree(17, [])
>>> t1.num_positives()
1
>>> t2 = Tree(-10, [])
>>> t2.num_positives()
0
>>> t3 = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])])
>>> t3.num_positives()
2
"""
if self.is_empty():
return 0
ans = 1 if self._root > 0 else 0
for subtree in self._subtrees:
ans = ans + subtree.num_positives()
return ans
def maximum(self: Tree) -> int:
"""Return the maximum item stored in this tree.
Return 0 if this tree is empty.
Precondition: all values in this tree are positive integers.
>>> t1 = Tree(17, [])
>>> t1.maximum()
17
>>> t3 = Tree(1, [Tree(12, []), Tree(10, []), Tree(30, [])])
>>> t3.maximum()
30
"""
if self.is_empty():
return 0
ans = self._root
for subtree in self._subtrees:
ans = max(subtree.maximum(), ans)
return ans
def height(self: Tree) -> int:
"""Return the height of this tree.
Please refer to the prep readings for the definition of tree height.
>>> t1 = Tree(17, [])
>>> t1.height()
1
>>> t2 = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])])
>>> t2.height()
2
"""
if self.is_empty():
return 0
h = 0
for subtree in self._subtrees:
h = max(subtree.height(), h)
return h + 1
def __contains__(self, item: Any) -> bool:
"""Return whether this tree contains <item>.
>>> t = Tree(1, [Tree(-2, []), Tree(10, []), Tree(-30, [])])
>>> t.__contains__(-30) # Could also write -30 in t.
True
>>> t.__contains__(148)
False
"""
if self.is_empty():
return False
if self._subtrees == []:
return self._root == item
if self._root == item:
return True
for subtree in self._subtrees:
if subtree.__contains__(item):
return True
return False
if __name__ == '__main__':
import doctest
doctest.testmod()
import python_ta
python_ta.check_all()
```

Output:

The above report opens in the browser after all errors are checked by the python_ta module.

Create an add method for the BST (Binary Search Tree) class.
add(self, new_value: object) -> None:
"""This method adds new value to the tree, maintaining BST
property. Duplicates must be allowed and placed in the right
subtree."""
Example #1: tree = BST()
print(tree) tree.add(10)
tree.add(15)
tree.add(5)
print(tree)
tree.add(15)
tree.add(15)
print(tree)
tree.add(5)
print(tree)
Output:
TREE in order { }
TREE in order { 5, 10, 15 }
TREE in order { 5, 10, 15, 15, 15 }
TREE in order {...

Instructions:
SLLStack (12 pts)
● Using the two properties below, implement the stack
interface using the SLLNode class from
Lab 2:
○ top_node → SLLNode object or None
○ size → int, keep track of stack size
● Implement the push( ), pop(
), top( ) methods
● Use SLLNode methods:
get_item( ), set_item( ), get_next(
), set_next( )
● (5 pts) In push(item):
○ Create new SLLNode with item
○ Add new node before top node
○ Update top_node...

Complete the redblacktree in Java.
Add a public boolean isBlack field to the Node inner
class. Make every Node object have a false isBlack field, all new
node is red by default.
In the end of the insert method, set the root node of
your red black tree to be black.
Implement the rotate() and recolor() functions, and
create tests for them in a separate class.
import java.util.LinkedList;
public class BinarySearchTree<T extends
Comparable<T>> {
protected static class Node<T> {
public...

import java.util.ArrayList;
/*
Rules:
1. Allow Tester to iterate
through all nodes using the in-order traversal as the
default.
This
means, in Tester the following code should work for an instance of
this class
called bst
that is storing Student objects for the data:
BinarySearchTree_Lab08<String> bst = new
BinarySearchTree_Lab08<String>();
bst.add("Man");
bst.add("Soda"); bst.add("Flag");
bst.add("Home");
bst.add("Today"); bst.add("Jack");
...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 8 minutes ago

asked 48 minutes ago

asked 54 minutes ago

asked 54 minutes ago

asked 55 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 4 hours ago