Как реализовать функции height() и count_leaves() в моем двоичном дереве поиска (BST) на Python? ⇐ Python

[Anonymous]

Я изучаю двоичные деревья поиска на Python и написал большинство функций BST, таких как вставка, поиск, find_min, find_max и удаление.
Мне нужна только помощь в реализации двух функций:

• height()
• count_leaves()

Ниже приведен мой полный код.

Может ли кто-нибудь показать мне, как правильно написать эти две недостающие функции?
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None

class BST:
def __init__(self):
self.root = None

# Insert a new key into the BST
def insert(self, key):
if self.root is None:
self.root = Node(key)
else:
self._insert(self.root, key)

def _insert(self, root, key):
if key < root.key:
if root.left is None:
root.left = Node(key)
else:
self._insert(root.left, key)
else:
if root.right is None:
root.right = Node(key)
else:
self._insert(root.right, key)

# Search for a key in the BST
def search(self, key):
return self._search(self.root, key)

def _search(self, root, key):
if root is None:
return False
if root.key == key:
return True
elif key < root.key:
return self._search(root.left, key)
else:
return self._search(root.right, key)

# Find minimum key in the BST
def find_min(self):
current = self.root
if current is None:
return None
while current.left:
current = current.left
return current.key

# Find maximum key in the BST
def find_max(self):
current = self.root
if current is None:
return None
while current.right:
current = current.right
return current.key

# Delete key from BST
def delete(self, key):
self.root = self.delete_Node(self.root, key)

def delete_Node(self, root, key):
if root is None:
return None

if key < root.key:
root.left = self.delete_Node(root.left, key)
elif key > root.key:
root.right = self.delete_Node(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left

current = root.right
while current.left:
current = current.left

root.key = current.key
root.right = self.delete_Node(root.right, current.key)

return root

# TODO: Implement height()
def height(self):
pass

# TODO: Implement count_leaves()
def count_leaves(self):
pass

# Driver Code
if __name__ == "__main__":
bst = BST()
roll_numbers = [51, 64, 72, 84, 61, 60, 79, 91, 76]
for num in roll_numbers:
bst.insert(num)

print("BST created successfully!")
print("Search 40:", bst.search(40))
print("Minimum roll number:", bst.find_min())
print("Maximum roll number:", bst.find_max())
bst.delete(72)
print("After deleting 72:", bst.search(72))
print("Height:", bst.height())


Подробнее здесь: https://stackoverflow.com/questions/798 ... earch-tree