Escreva uma função não-recursiva que retorne o menor valor de uma árvore binária (não ordenada)
Passo 1
A questão pede para escrever uma função iterativa (não-recursiva) que percorra uma árvore binária genérica (não ordenada) e retorne o menor valor armazenado em qualquer dos seus nós. O conteúdo principal aqui é varredura completa de árvore (tree traversal) usando uma estrutura auxiliar (pilha ou fila).
Passo 2
Vamos representar cada nó da árvore com um objeto que tenha os atributos
valor
, esquerda
e direita
. A função terá assinatura como menor_valor(arvore)
e receberá a raiz da árvore. Para percorrer sem recursão, vamos usar uma pilha (stack) que armazena nós ainda a visitar.Passo 3
Inicializamos verificando se a raiz é nula. Se for, podemos retornar
None
ou lançar uma exceção, pois não há valor a retornar. Caso contrário, criamos a pilha contendo apenas o nó raiz e definimos min_val
igual a arvore.valor
.Passo 4
Enquanto a pilha não estiver vazia, retiramos (pop) o nó do topo. Comparamos o valor desse nó com
min_val
e atualizamos min_val
caso seja menor. Em seguida, empilhamos seus filhos não nulos (primeiro esquerda, depois direita, ou vice-versa — a ordem não afeta o resultado).Passo 5
Quando a pilha esvaziar, já teremos visitado todos os nós. Neste ponto,
min_val
conterá o menor valor encontrado, e podemos retorná-lo.Resposta
def menor_valor(arvore):
# Se a árvore estiver vazia, não há valor a retornar
if arvore is None:
return None
# Se a árvore estiver vazia, não há valor a retornar
if arvore is None:
return None
# Inicializa min_val com o valor da raiz e prepara a pilha
min_val = arvore.valor
stack = [arvore]
# Percorre toda a árvore de forma iterativa
while stack:
nodo = stack.pop()
# Atualiza o menor valor se encontrar um valor menor
if nodo.valor < min_val:
min_val = nodo.valor
# Empilha filhos não nulos para continuar a varredura
if nodo.direita is not None:
stack.append(nodo.direita)
if nodo.esquerda is not None:
stack.append(nodo.esquerda)
return min_val