Insérer un nœud dans un arbre de recherche binaire
Dans la vidéo, vous avez appris ce que sont les arbres de recherche binaires (BST) et comment mettre en œuvre leurs principales opérations.
Dans cet exercice, vous mettrez en œuvre une fonction permettant d'insérer un nœud dans un site BST.
Pour tester votre code, vous pouvez utiliser l'arbre suivant :
Les nœuds contiennent des titres de livres, ce qui permet de construire un site BST basé sur l'ordre alphabétique.
Cet arbre a été préchargé dans la variable bst:
bst = CreateTree()
Vous pouvez vérifier si le nœud est correctement inséré à l'aide de ce code :
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Cet exercice fait partie du cours
Structures de données et algorithmes en Python
Instructions
- Vérifiez si le site BST est vide.
- Vérifie si les données à insérer sont plus petites que les données du nœud actuel.
- Vérifie si les données à insérer sont supérieures aux données du nœud actuel.
Exercice interactif pratique
Essayez cet exercice en complétant cet exemple de code.
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"))