Einen Knoten in einen binären Suchbaum einfügen
Im Video hast du gelernt, was binäre Suchbäume (BSTs) sind und wie man ihre wichtigsten Operationen implementiert.
In dieser Übung implementierst du eine Funktion zum Einfügen eines Knotens in eine BST.
Um deinen Code zu testen, kannst du den folgenden Baum verwenden:
Die Knotenpunkte enthalten Buchtitel und bilden eine BST, die auf der alphabetischen Reihenfolge basiert.
Dieser Baum wurde in der Variable bst vorgeladen:
bst = CreateTree()
Mit diesem Code kannst du überprüfen, ob der Knoten korrekt eingefügt wurde:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Diese Übung ist Teil des Kurses
Datenstrukturen und Algorithmen in Python
Anleitung zur Übung
- Prüfe, ob die BST leer ist.
- Prüfe, ob die einzufügenden Daten kleiner sind als die Daten des aktuellen Knotens.
- Prüfe, ob die einzufügenden Daten größer sind als die Daten des aktuellen Knotens.
Interaktive Übung zum Anfassen
Probieren Sie diese Übung aus, indem Sie diesen Beispielcode ausführen.
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"))