Infoga en nod i ett binärt sökträd
I videon lärde du dig vad binära sökträd (BST:er) är och hur man implementerar deras grundläggande operationer.
I den här övningen implementerar du en funktion för att infoga en nod i ett BST.
För att testa din kod kan du använda följande träd:
Noderna innehåller boktitlar och bygger upp ett BST baserat på alfabetisk ordning.
Detta träd har förinslästs i variabeln bst:
bst = CreateTree()
Du kan kontrollera att noden infogas korrekt med den här koden:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Den här övningen är en del av kursen
Datastrukturer och algoritmer i Python
Övningsinstruktioner
- Kontrollera om BST:en är tom.
- Kontrollera om den data som ska infogas är mindre än den aktuella nodens data.
- Kontrollera om den data som ska infogas är större än den aktuella nodens data.
Interaktiv övning med praktiskt arbete
Testa den här övningen genom att slutföra den här exempelkoden.
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"))