Faça uma função que, dada uma árvore binária de busca, retorne a quantidade de nós que guardam números primos.
Passo 1
A questão pede uma função que, dada uma árvore binária de busca (ABB), conte quantos nós armazenam números primos. O conteúdo envolve estrutura de dados em árvore, travessia recursiva e teste de primalidade.
Passo 2
Para verificar se um número é primo, vamos criar uma função isPrimo(n). A ideia é: se n ≤ 1, não é primo; se n = 2, é primo; se for par e maior que 2, não é primo; senão testar divisores ímpares de 3 até √n.
Para percorrer a ABB e contar primos, podemos usar uma abordagem recursiva. Em cada nó, contamos 1 se o valor for primo (usando isPrimo) e somamos o resultado das chamadas recursivas para os filhos esquerdo e direito.
A função principal countPrimos(raiz) deve tratar o caso base (árvore vazia retorna 0) e, caso contrário, aplicar o passo anterior para acumular o total de nós primos.
Para percorrer a ABB e contar primos, podemos usar uma abordagem recursiva. Em cada nó, contamos 1 se o valor for primo (usando isPrimo) e somamos o resultado das chamadas recursivas para os filhos esquerdo e direito.
A função principal countPrimos(raiz) deve tratar o caso base (árvore vazia retorna 0) e, caso contrário, aplicar o passo anterior para acumular o total de nós primos.
Passo 3
A complexidade fica em O(N·√M), onde N é o número de nós e M é o maior valor armazenado, e o uso de recursão consome O(h) de memória, com h sendo a altura da árvore.
Resposta
def isPrimo(n):
# Casos triviais
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
# Testar divisores ímpares até a raiz de n
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
# Casos triviais
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
# Testar divisores ímpares até a raiz de n
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
def countPrimos(raiz):
# Se o nó for nulo, não há primos
if raiz is None:
return 0
# Conta no nó atual e nos subárvores
contador_atual = 1 if isPrimo(raiz.valor) else 0
return contador_atual + countPrimos(raiz.esquerda) + countPrimos(raiz.direita)
# Se o nó for nulo, não há primos
if raiz is None:
return 0
# Conta no nó atual e nos subárvores
contador_atual = 1 if isPrimo(raiz.valor) else 0
return contador_atual + countPrimos(raiz.esquerda) + countPrimos(raiz.direita)