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 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
# 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)

Exercícios relacionados