"""
-------------------------------------------------------
Popularity Tree class.
-------------------------------------------------------
Author: David Brown
ID: 999999999
Email:
[email protected]
__updated__ = "2020
...
"""
-------------------------------------------------------
Popularity Tree class.
-------------------------------------------------------
Author: David Brown
ID: 999999999
Email:
[email protected]
__updated__ = "2020-04-11"
-------------------------------------------------------
Linked class version of the Popularity_Tree (PT) ADT.
-------------------------------------------------------
"""
from copy import deepcopy
class _PT_Node:
def __init__(self, value):
"""
-------------------------------------------------------
Initializes a PT node containing value. Child pointers
are None, height is 1, count is 1
Use: node = _PT_Node(value)
-------------------------------------------------------
Parameters:
value - value for the node (?)
Returns:
A _PT_Node object (_PT_Node)
-------------------------------------------------------
"""
self._value = deepcopy(value)
self._left = None
self._right = None
self._height = 1
self._rcount = 1 # Retrieval count
return
def _update_height(self):
"""
-------------------------------------------------------
Updates the height of the current node. _height is 1 plus
the maximum of the node's (up to) two child heights.
Use: node._update_height()
-------------------------------------------------------
Returns:
None
-------------------------------------------------------
"""
if self._left is None:
left_height = 0
else:
left_height = self._left._height
if self._right is None:
right_height = 0
else:
right_height = self._right._height
self._height = max(left_height, right_height) + 1
This study source was downloaded by 100000793680026 from CourseHero.com on 04-20-2021 18:14:49 GMT -05:00
https://www.coursehero.com/file/60414938/Popularity-Tree-linkedtxt/
This study resource was
shared via CourseHero.comreturn
class Popularity_Tree:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty PT.
Use: pt = PT()
-------------------------------------------------------
Returns:
A PT object (PT)
-------------------------------------------------------
"""
self._root = None
self._count = 0
return
def is_empty(self):
"""
-------------------------------------------------------
Determines if pt is empty.
Use: b = pt.is_empty()
-------------------------------------------------------
Returns:
True if pt is empty, False otherwise.
-------------------------------------------------------
"""
return self._root is None
def __len__(self):
"""
-------------------------------------------------------
Returns the number of nodes in the PT.
Use: n = len(pt)
-------------------------------------------------------
Returns:
the number of nodes in pt.
-------------------------------------------------------
"""
return self._count
def height(self):
"""
-------------------------------------------------------
Returns the maximum height of a PT, i.e. the length of the
longest path from root to a leaf node in the tree.
Use: h = pt.height()
-------------------------------------------------------
Returns:
h - maximum height of pt (int)
-------------------------------------------------------
"""
if self._root is None:
h = 0
else:
h = self._root._height
return h
This study source was downloaded by 100000793680026 from CourseHero.com on 04-20-2021 18:14:49 GMT -05:00
https://www.coursehero.com/file/60414938/Popularity-Tree-linkedtxt/
This study
