Insertion d'un nœud dans un arbre binaire de recherche
Dans la vidéo, vous avez appris ce que sont les arbres binaires de recherche (ABR) et comment en implémenter les principales opérations.
Dans cet exercice, vous implémenterez une fonction pour insérer un nœud dans un ABR.
Pour tester votre code, vous pouvez utiliser l'arbre suivant :
Les nœuds contiennent des titres de livres, formant un ABR selon 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é avec ce code :
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Cette activité fait partie du cours
Structures de données et algorithmes en Python
Instructions de l’exercice
- Vérifiez si l'ABR est vide.
- Vérifiez si la donnée à insérer est plus petite que la donnée du nœud courant.
- Vérifiez si la donnée à insérer est plus grande que la donnée du nœud courant.
Exercice interactif pratique
Essayez cet exercice en complétant ce code d’exemple.
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"))