Mostrando postagens com marcador Árvores Binárias. Mostrar todas as postagens
Mostrando postagens com marcador Árvores Binárias. Mostrar todas as postagens

sexta-feira, 31 de maio de 2013

Número de folhas em uma Árvore Binária

Neste post, vamos descrever indutivamente um algoritmo que calcula o número de folhas em uma árvore binária. Vamos novamente utilizar indução.

Descrição indutiva:
  • Caso base: uma árvore binária vazia não possui folhas, uma árvore com apenas um nó, possui uma folha.
  • Hipótese de indução: caso a árvore não seja vazia, podemos assumir que já temos a quantidade de folhas nas subárvores esquerda e direita. (isso mesmo, o número de folhas nas subárvores caíram do céu =) ).
  • Caso Geral: é trivial, pois basta somar os valores encontrados pela hipótese de indução.
O algoritmo segue EXATAMENTE a ideia apresentada acima.

  • Implementação em C++
int numFolhas(ARVORE *raiz){
  if(raiz == null)
    return 0;
  else
    if(raiz->esq == raiz->dir)
      return 1;
   else
      return numFolhas(raiz->esq) + numFolhas(raiz->dir);
}

terça-feira, 26 de junho de 2012

Altura de Árvores Binárias: uma abordagem indutiva

Agora vamos criar um algoritmo que nos diz a altura de uma árvore binária. A altura de uma árvore binária pode ser definida como:
  • Comprimento do maior caminho que vai da raiz até um nó folha. Onde o comprimento de um caminho é determinado pelo número de arestas que ele possui.
A árvore abaixo possui altura 3.


Para construir nosso algoritmo vamos mais uma vez recorrer a abordagem indutiva.
Idéia indutiva
  • Caso Base: a altura de uma árvore vazia, ou com apenas um nó, é igual a zero.
  • Hipótese de Indução: podemos assumir que já temos as alturas das subárvores esquerda e direita.
  • Caso Geral: a altura da árvore será a maior dentre as alturas encontradas pela hipótese de indução mais 1.

A implementação a seguir decorre da idéia indutiva apresentada acima.

  • Implementação em Python
def height(tree):
  if tree.left == tree.right: return 0   # arvore vazia
  if height(tree.left) > height(tree.right): return height(tree.left) + 1
  return height(tree.right) + 1

  • Implementação em C++
int height(ARVORE *t){
  if(t == NULL || t->esq == t->dir)
    return 0;
  else
    return max(height(t->esq), height(t->dir)) + 1;
}

quinta-feira, 21 de junho de 2012

Definição indutiva de Árvores Binárias

Saber manipular uma estrutura de dados corretamente é imprescindível para qualquer programador. E com árvores binárias não pode ser diferente, principalmente quando nos deparamos com problemas cuja natureza exige uma  estrutura de dados não linear e que permita uma hierarquização dos dados que serão manipulados.
Indutivamente, podemos definir uma árvore binária T como sendo:
  • Uma árvore vazia, ou
  • Um nó especial r, chamado raiz de T, com duas subárvores Te e Td. Onde Te e Td são as subárvores esquerda e direita respectivamente.

Podemos tirar proveito da definição acima na hora de construir algoritmos que manipulam árvores. Para isso, basta assumir que o problema que desejamos resolver, já está resolvido para as subárvores esquerda e direita. Por exemplo, vamos supor que desejamos somar os valores armazenados em todos os vértices de uma árvore binária. Usando indução, a solução é a seguinte:
  • Caso Base: a soma dos nós de uma árvore vazia é zero.
  • Hipótese de Indução: assumimos que já temos a soma de todos os valores armazenados nas subárvores esquerda e direita.
  • Caso Geral: é quase trivial, pois simplesmente somamos o valor armazenado na raiz com os valores que por hipótese de indução são as somas das subárvores esquerda e direita.
A implementação decorre "diretamente" do esquema apresentado acima:

  • Implementação em C++
int somaNos(ARVORE t)
{
  if(t == NULL)
    return 0;
  else
    return t->info + somaNos(t->esq) + somaNos(t->dir); 
}

segunda-feira, 18 de junho de 2012

Caminhamento indutivo em Árvores Binárias

Neste post vamos construir indutivamente algoritmos que realizam os caminhamentos "pré-ordem", "em-ordem" e "pós-ordem" em árvores binárias. Tais algoritmos são similares, diferindo apenas na ordem em que as chamadas recursivas, que são representantes diretas da hipótese de indução, aparecem.
  • Pré-Ordem: visita a raiz, em seguida a subárvore da esquerda e a subárvore da direita.
  • Em-Ordem: visita a subárvore da esquerda, e em seguida a raiz e a subárvore da direita.
  • Pós-Ordem: vista a subárvore da esquerda, e em seguida a subárvore da direita e a raiz.

O resultado dos caminhamentos aplicados a árvore acima são os seguintes:
  • Pré-Ordem: A | B | D | E | C | F | G
  • Em-Ordem: D | B | E | A | F | C | G
  • Pós-Ordem: D | E | B | F | G | C | A
Agora vamos derivar o nosso algoritmo indutivamente.
Idéia indutiva
  • Caso base: é trivial, pois não fazemos caminhamento em árvores binárias vazias.
  • Hipótese de Indução: podemos assumir que já temos os caminhamentos das subárvores esquerda e direita.
  • Caso Geral: Usando as respostas dadas pela hipótese de indução, basta definir quem será impresso/visitado primeiro. Seguindo o esquema dos três tipos de caminhamento apresentados acima.
As implementações são imediatas, pois já sabemos "o que fazer". A partir de agora nos preocuparemos com os detalhes de implementação.

Caminhamento pré-ordem
  • Implementação em C++
void preOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     cout << t->info << ' ';
     preOrdem(t->esq);
     preOrdem(t->dir);
  }
}
Caminhamento em-ordem
  • Implementação em C++
void emOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     emOrdem(t->esq);
     cout << t->info << ' ';
     emOrdem(t->dir);
  }
}
Caminhamento pós-ordem
  • Implementação em C++
void posOrdem(ARVORE *t)
{
  if(t != NULL)
  {
     posOrdem(t->esq);
     posOrdem(t->dir);
     cout << t->info << ' ';
  }
}