CP 164Popularity_Tree_linked(GRADED A)

Document Content and Description Below

""" ------------------------------------------------------- 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 [Show More]

Last updated: 3 years ago

Preview 1 out of 7 pages