Implementar uma função não-recursiva para calcular o tamanho de uma árvore binária.
Passo 1
O enunciado pede uma função não-recursiva para calcular o número de nós (tamanho) de uma árvore binária. O conteúdo envolve estruturas de dados (árvores e pilhas) e travessia iterativa de árvores, então vamos precisar de uma pilha explícita para simular a chamada recursiva.
Passo 2
O tamanho de uma árvore binária é a quantidade total de nós que ela contém. Recursivamente, faríamos
, mas aqui vamos usar uma abordagem iterativa: percorrendo todos os nós com uma pilha, incrementando um contador a cada visita.
Passo 3
A ideia é usar uma travessia em pré-ordem (visita o nó antes dos filhos) simulada por uma pilha. Colocamos a raiz na pilha, e enquanto ela não estiver vazia, retiramos o topo, contamos esse nó e empilhamos primeiro o filho direito e depois o esquerdo.
Passo 4
Algoritmo passo a passo: 1) Se a árvore estiver vazia (raiz
NULL), retorna 0. 2) Inicializa contador
e cria uma pilha vazia. 3) Empilha a raiz. 4) Enquanto a pilha não estiver vazia: a) Desempilha um nó
. b) Incrementa
. c) Se $node->right \neq $ NULL, empilha
. d) Se $node->left \neq $ NULL, empilha
. 5) Quando o laço terminar,
terá o tamanho da árvore.
Passo 5
A implementação em pseudocódigo/C fica assim:
int size(TreeNode* root) {
if (root == NULL) {
return 0;
}
int count = 0;
Stack* stack = createStack();
push(stack, root);
while (!isEmpty(stack)) {
TreeNode* node = pop(stack);
count++;
if (node->right != NULL) {
push(stack, node->right);
}
if (node->left != NULL) {
push(stack, node->left);
}
}
destroyStack(stack);
return count;
}
Resposta
int size(TreeNode* root) {
if (root == NULL) {
return 0;
}
int count = 0;
Stack* stack = createStack();
push(stack, root);
while (!isEmpty(stack)) {
TreeNode* node = pop(stack);
count++;
if (node->right != NULL) {
push(stack, node->right);
}
if (node->left != NULL) {
push(stack, node->left);
}
}
destroyStack(stack);
return count;
}