Вставляння вузла до бінарного дерева пошуку
У відео ви дізналися, що таке бінарні дерева пошуку (BST) і як реалізувати їхні основні операції.
У цій вправі ви реалізуєте функцію для вставляння вузла до BST.
Щоб протестувати свій код, скористайтеся таким деревом:
Вузли містять назви книжок, формуючи BST за абетковим порядком.
Це дерево попередньо завантажене в змінну bst:
bst = CreateTree()
Ви можете перевірити, чи вузол вставлено коректно, цим кодом:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Ця вправа є частиною курсу
Структури даних і алгоритми в Python
Інструкції до вправи
- Перевірте, чи порожнє BST.
- Перевірте, чи дані для вставляння менші за дані поточного вузла.
- Перевірте, чи дані для вставляння більші за дані поточного вузла.
Інтерактивна практична вправа
Спробуйте виконати цю вправу, доповнивши цей зразок коду.
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
new_node = TreeNode(data)
# Check if the BST is empty
if ____ == None:
self.root = new_node
return
else:
current_node = self.root
while True:
# Check if the data to insert is smaller than the current node's data
if ____ < ____:
if current_node.left_child == None:
current_node.left_child = new_node
return
else:
current_node = current_node.left_child
# Check if the data to insert is greater than the current node's data
elif ____ > ____:
if current_node.right_child == None:
current_node.right_child = new_node
return
else:
current_node = current_node.right_child
bst = CreateTree()
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))