Inserción de un nodo en un árbol binario de búsqueda
En el vídeo has aprendido qué son los árboles de búsqueda binarios (BST) y cómo implementar sus principales operaciones.
En este ejercicio, implementarás una función para insertar un nodo en un BST.
Para probar tu código, puedes utilizar el siguiente árbol:
Los nodos contienen títulos de libros, que crean un BST basado en el orden alfabético.
Este árbol se ha precargado en la variable bst:
bst = CreateTree()
Puedes comprobar si el nodo está correctamente insertado con este código:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Este ejercicio forma parte del curso
Estructuras de datos y algoritmos en Python
Instrucciones de ejercicio
- Comprueba si el BST está vacío.
- Comprueba si los datos que se van a insertar son menores que los datos del nodo actual.
- Comprueba si los datos que se van a insertar son mayores que los datos del nodo actual.
Ejercicio interactivo práctico
Pruebe este ejercicio completando este código de muestra.
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"))