Wstawianie węzła do drzewa wyszukiwania binarnego
W lekcji wideo poznałeś drzewa wyszukiwania binarnego (BST) i sposoby implementacji ich głównych operacji.
W tym ćwiczeniu zaimplementujesz funkcję wstawiającą węzeł do BST.
Aby przetestować kod, możesz skorzystać z poniższego drzewa:
Węzły zawierają tytuły książek – BST jest zbudowane na podstawie kolejności alfabetycznej.
Drzewo zostało wcześniej załadowane do zmiennej bst:
bst = CreateTree()
Poprawność wstawienia węzła możesz sprawdzić za pomocą poniższego kodu:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
To ćwiczenie jest częścią kursu
Struktury danych i algorytmy w Pythonie
Instrukcje do ćwiczenia
- Sprawdź, czy BST jest puste.
- Sprawdź, czy dane do wstawienia są mniejsze od danych bieżącego węzła.
- Sprawdź, czy dane do wstawienia są większe od danych bieżącego węzła.
Interaktywne ćwiczenie praktyczne
Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.
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"))