Uma ABB é estritamente binária se todos os nós da árvore tem 2 filhos. Implemente uma função que verifica se uma ABB é estritamente binária.
Passo 1
O enunciado pede uma função que, dada uma ABB, retorne se ela é estritamente binária, isto é, todos os nós internos têm exatamente dois filhos (e folhas têm zero filhos). Vamos usar recursão para visitar cada nó e aplicar essa condição.
Passo 2
Base case: se o nó atual for None (árvore vazia ou chegamos além de uma folha), consideramos que essa parte é estritamente binária e retornamos True.
Passo 3
Em cada chamada recursiva, verificamos se o nó tem exatamente um filho (esquerdo ou direito). Se tiver só um, já podemos retornar False imediatamente, pois viola a definição.
Passo 4
Se o nó tiver zero filhos (é folha) ou dois filhos, continuamos a verificação recursiva em ambos os subárvores e retornamos a conjunção (AND) dos resultados.
Passo 5
A função principal simplesmente chama essa rotina a partir da raiz da ABB e devolve o resultado.
Passo 6
Abaixo está a implementação em Python.
Resposta
class Node:
def init(self, key):
self.key = key
self.left = None
self.right = None
def init(self, key):
self.key = key
self.left = None
self.right = None
def is_strictly_binary(node):
“”"
Retorna True se a árvore cujo nó raiz é ‘node’ for estritamente binária,
ou seja, cada nó interno tem exatamente dois filhos.
“”"
# Caso base: árvore vazia ou chegamos além de uma folha
if node is None:
return True
“”"
Retorna True se a árvore cujo nó raiz é ‘node’ for estritamente binária,
ou seja, cada nó interno tem exatamente dois filhos.
“”"
# Caso base: árvore vazia ou chegamos além de uma folha
if node is None:
return True
# Se tiver exatamente um filho, falha
if (node.left is None) != (node.right is None):
return False
# Se for folha (dois filhos None) ou nó com dois filhos, verifica recursivamente
return is_strictly_binary(node.left) and is_strictly_binary(node.right)