Suponha que o método numNodes() é definido por: Quais das instruções seguintes poderia substituir <code>, correctamente, no referido método?

Alternativa B

O problema apresenta um método recursivo em C++ para contar o número de nós em uma árvore binária. A lógica correta para calcular o tamanho de uma árvore é somar o nó atual (raiz da subárvore) com os nós das subárvores esquerda e direita.

Análise das Instruções

Para resolver a questão, precisamos verificar qual instrução preenche corretamente a lacuna <código> dentro do bloco else, onde tree não é nulo.

• Instrução I:

    return 1 + numNodes(tree->left) + numNodes(tree->right);

Esta opção está correta. Ela conta o nó atual (1) e soma recursivamente o resultado dos chamados nas subárvores esquerda (tree->left) e direita (tree->right). A fórmula geral é:
\text{Total} = 1 + \text{Esquerda} + \text{Direita}

• Instrução II:

    return numNodes(tree) + numNodes(tree->left) + numNodes(tree->right);

Esta opção está incorreta. Ao chamar numNodes(tree) novamente sem alterar o ponteiro ou a condição de parada, cria-se uma recursão infinita, resultando em estouro de pilha (stack overflow), pois a função chama a si mesma indefinidamente.

• Instrução III:

    return numNodes(tree->left) + numNodes(tree->right);

Esta opção está incorreta. Ela soma apenas as subárvores, ignorando o nó raiz da chamada atual. Isso faria com que o contador ficasse sempre inferior ao valor real por exatamente 1 unidade (para cada nó visitado no topo da pilha).

Conclusão

Apenas a instrução I implementa a lógica correta de contagem de nós em uma estrutura de árvore recursiva. Portanto, a alternativa correta é a que indica "Apenas I".

Alternativa B