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 1 + tamanho(esquerda) + tamanho(direita), 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 count = 0 e cria uma pilha vazia. 3) Empilha a raiz. 4) Enquanto a pilha não estiver vazia: a) Desempilha um nó node. b) Incrementa count. c) Se $node->right \neq $ NULL, empilha node->right neq . d) Se $node->left \neq $ NULL, empilha node->right. 5) Quando o laço terminar, node-><=ft neq 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;
}

Exercícios relacionados