Escreva uma função que exclui todos os nós de uma árvore binária de busca com ID par.
Passo 1
Estamos com uma árvore binária de busca (BST) e queremos escrever uma função que remova todos os nós cujo campo ID seja par.
Passo 2
Para percorrer todos os nós e decidir quais excluir, podemos usar uma travessia recursiva (por exemplo, pós-ordem), de forma que ao visitar cada nó já tenhamos processado seus filhos.
Para excluir um nó na BST, precisamos lidar com três casos: nó folha (sem filhos), nó com um filho e nó com dois filhos. No caso de dois filhos, substituímos o valor do nó pelo valor mínimo da subárvore direita (sucessor) e removemos esse sucessor recursivamente.
Para excluir um nó na BST, precisamos lidar com três casos: nó folha (sem filhos), nó com um filho e nó com dois filhos. No caso de dois filhos, substituímos o valor do nó pelo valor mínimo da subárvore direita (sucessor) e removemos esse sucessor recursivamente.
Passo 3
Vamos implementar primeiro uma função auxiliar delete_node(root, key) que exclui o nó de valor key na BST mantendo a propriedade de busca.
Por fim, escrevemos a função remove_even_nodes(root) que faz uma pós-ordem: visita filhos, e então, se root.id for par, chama delete_node para excluí-lo.
Por fim, escrevemos a função remove_even_nodes(root) que faz uma pós-ordem: visita filhos, e então, se root.id for par, chama delete_node para excluí-lo.
Passo 4
Resultado final: a função remove_even_nodes retorna a nova raiz da BST sem nós de ID par.
Resposta
Definição de um nó da BST
class Node:
def init(self, id, left=None, right=None):
self.id = id
self.left = left
self.right = right
def init(self, id, left=None, right=None):
self.id = id
self.left = left
self.right = right
Função auxiliar para deletar um nó com valor key
def delete_node(root, key):
if root is None:
return None
if key < root.id:
root.left = delete_node(root.left, key)
elif key > root.id:
root.right = delete_node(root.right, key)
else:
# Caso 1: sem filhos
if root.left is None and root.right is None:
return None
# Caso 2: um filho
if root.left is None:
return root.right
if root.right is None:
return root.left
# Caso 3: dois filhos -> encontrar sucessor (mínimo à direita)
succ = root.right
while succ.left:
succ = succ.left
root.id = succ.id
root.right = delete_node(root.right, succ.id)
return root
if root is None:
return None
if key < root.id:
root.left = delete_node(root.left, key)
elif key > root.id:
root.right = delete_node(root.right, key)
else:
# Caso 1: sem filhos
if root.left is None and root.right is None:
return None
# Caso 2: um filho
if root.left is None:
return root.right
if root.right is None:
return root.left
# Caso 3: dois filhos -> encontrar sucessor (mínimo à direita)
succ = root.right
while succ.left:
succ = succ.left
root.id = succ.id
root.right = delete_node(root.right, succ.id)
return root