Em uma árvore binária, faça um algoritmo para alterar o valor de cada nó (exceto nó folha) para a soma dos valores dos nós esquerda e direita.

Passo 1

O enunciado pede para alterar o valor de cada nó interno (não-folha) de uma árvore binária de modo que passe a ser a soma dos valores de seus filhos esquerdo e direito. O conteúdo envolvido é Árvores Binárias e Recursão, e vamos precisar fazer um percurso em pós-ordem para processar primeiro os filhos antes de atualizar o nó pai.

Passo 2

Para não perdermos o valor original dos filhos (que serão usados na soma), nossa função recursiva deve retornar o valor antiga do nó antes da atualização. Assim, ao subirmos na recursão, o pai recebe exatamente o valor original que o filho tinha.
A lógica central é: se o nó for nulo, retornamos 0 (ou ignoramos); se for folha, retornamos seu valor sem alterar; caso contrário, chamamos recursivamente para o filho esquerdo e direito, guardamos os valores retornados (originais), atualizamos o nó atual com essa soma e então retornamos o valor original do nó para quem o chamou.

Passo 3

Segue o pseudocódigo do algoritmo em estilo recursivo:
função atualizarValor(nó):
se nó == nulo:
retornar 0
se nó.esquerda == nulo e nó.direita == nulo: // caso folha
retornar nó.valor
valorOriginal ← nó.valor
somaEsquerda ← atualizarValor(nó.esquerda)
somaDireita ← atualizarValor(nó.direita)
nó.valor ← somaEsquerda + somaDireita
retornar valorOriginal

Resposta

A função atualizarValor deve ser chamada passando a raiz da árvore para que, em pós-ordem, cada nó interno receba a soma dos valores originais de seus filhos.

Exercícios relacionados