Inserção de um nó em uma árvore de pesquisa binária
No vídeo, você aprendeu o que são árvores de pesquisa binárias (BSTs) e como implementar suas principais operações.
Neste exercício, você implementará uma função para inserir um nó em um site BST.
Para testar seu código, você pode usar a seguinte árvore:
Os nós contêm títulos de livros, criando um BST com base na ordem alfabética.
Essa árvore foi pré-carregada na variável bst:
bst = CreateTree()
Você pode verificar se o nó foi inserido corretamente com este código:
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))
Este exercício faz parte do curso
Estruturas de dados e algoritmos em Python
Instruções do exercício
- Verifique se o site BST está vazio.
- Verificar se os dados a serem inseridos são menores do que os dados do nó atual.
- Verifica se os dados a serem inseridos são maiores do que os dados do nó atual.
Exercício interativo prático
Experimente este exercício completando este código de exemplo.
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"))