Een knoop invoegen in een binaire zoekboom
In de video heb je geleerd wat binaire zoekbomen (BST’s) zijn en hoe je hun belangrijkste bewerkingen implementeert.
In deze oefening implementeer je een functie om een knoop in een BST in te voegen.
Om je code te testen, kun je de volgende boom gebruiken:
De knopen bevatten boektitels en vormen een BST op basis van alfabetische volgorde.
Deze boom is al voor je ingeladen in de variabele bst:
bst = CreateTree()
Je kunt controleren of de knoop correct is ingevoegd met deze code:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Deze oefening maakt deel uit van de cursus
Datastructuren en algoritmen in Python
Oefeninstructies
- Controleer of de BST leeg is.
- Controleer of de in te voegen data kleiner is dan de data van de huidige knoop.
- Controleer of de in te voegen data groter is dan de data van de huidige knoop.
Interactieve oefening met praktijkervaring
Probeer deze oefening door deze voorbeeldcode aan te vullen.
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"))