Vkládání uzlu do binárního vyhledávacího stromu
Ve videu sis osvojil/a, co jsou binární vyhledávací stromy (BST) a jak implementovat jejich hlavní operace.
V tomto cvičení implementuješ funkci pro vložení uzlu do BST.
Svůj kód můžeš otestovat na následujícím stromě:
Uzly obsahují názvy knih a BST je sestavený na základě abecedního pořadí.
Tento strom je předem načtený v proměnné bst:
bst = CreateTree()
Správnost vložení uzlu můžeš ověřit tímto kódem:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Toto cvičení je součástí kurzu
Datové struktury a algoritmy v Pythonu
Pokyny k cvičení
- Zjisti, zda je BST prázdný.
- Zkontroluj, zda jsou vkládaná data menší než data aktuálního uzlu.
- Zkontroluj, zda jsou vkládaná data větší než data aktuálního uzlu.
Interaktivní cvičení na vyzkoušení si v praxi
Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.
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"))