Árvores

O primeiro passo na implementação destas arvores consiste em definir num ficheiro de definições o tipo de dados das árvores binárias (de procura),
 

• Um nodo da árvore consiste numa estrutura com tres campos: o elemento a armazenar, e duas referencias para os filhos esquerdo e direito. O tipo de dados em C vai então ser definido do seguinte modo:

typedef struct nodo
{ ELEM e;
  struct nodo *esq;
  struct nodo *dir;
} NODO;
 
 

• O tipo da árvore é então definido como um apontador para um nodo:

typedef NODO * ARV;
 

•  Nesta implementação vamos considerar o caso mais simples: os elementos que armazenamos são do tipo inteiro.

 

typedef int ELEM;
 

• De seguida definimos uma serie de macros para  simplificar o acesso aos vários campos de um nodo da árvore, para detectar se uma árvore é vazia e para construir um novo nodo da árvore. Estas macros são depois usadas na implementação, tornando-a mais legível e simplificando o seu código.

#define ESQ(a)     a->esq
#define DIR(a)     a->dir
#define EL(a)      a->e
#define EMPTY(a)   (a == NULL)
#define CONS_NODO  (ARV)malloc(sizeof(NODO))

 

• No ficheiro de definições incluímos ainda o tipo das funções que manipulam as árvores binárias de procura. A sua implementação está codificada no ficheiro de implementação.

ARV      nova_arv ();
ARV      insere   (ARV a , ELEM e);
BOOLEAN  procura  (ARV a , ELEM e);
ARV      remover  (ARV a , ELEM e);

BOOLEAN  folha    (ARV a);
ELEM     Max      (ARV a);
ELEM     Min      (ARV a);

int      peso     (ARV a);

void     preorder (ARV a);
void     inorder  (ARV a , void (*f)(ELEM e));
 
 
 

• O ficheiro de implementação importa o ficheiro de definições:

#include "arvbin.h"
 
 

• Criar uma nova árvore corresponde a devolver um apontador nulo (i.e. uma árvore vazia)

ARV nova_arv()
{ return NULL;
}
 

• Inserir um elemento na árvore:
Caso I: árvore vazia
              Constroi um novo nodo
              O nodo e devolvido como sendo a nova árvore.
Caso II: árvore nao vazia
                 Se o elemento que esta no nodo árvore e menor que o elemento a inserir então
                     inserimos na subárvore direita
             Inserir na subárvore direita corresponde a
                    " o novo lado direito da árvore passa a ser o resultado de inserir no
                       lado direito (anterior) o elemento passado como parametro."
    O caso inverso é analogo
 
ARV insere (ARV a , ELEM e)
{ ARV nova;

  if EMPTY(a)
    { nova = CONS_NODO;
      ESQ(nova) = NULL;
      DIR(nova) = NULL;
      EL(nova)  = e;
      return nova;
    }
  else
    { if ( EL(a) < e )
        DIR(a) = insere(DIR(a),e);
      else
        ESQ(a) = insere(ESQ(a),e);  /* Repeticoes sao inseridas na esquerda! */
      return a;
    }
}
 
 

• A funcao que procura um elemento devolve falso se a árvore e vazia, ou verdade caso o elemento no nodo da árvore seja igual ao elemento a procurar. Caso o elemento seja menor  (maior) então o resultado da procura é o resultado de procurar no lado esquerdo (direito) do nodo.

 

BOOLEAN procura (ARV a , ELEM e)
{
  if EMPTY(a)          return FALSE;
  else
    if ( EL(a) == e )  return TRUE;
    else
      if ( EL(a) < e ) return procura (DIR(a),e);
      else             return procura (ESQ(a),e);
}

 

• Uma  funcao bastante útil sobre árvores consiste na visita de todos os seus nodos. Esta operação designa-se por travessia. Numa árvore binária existem varias hipoteses para efectuar essa travessia, por exemplo visitar o nodo pai, seguido de visitar a subárvore esquerda e por fim visitar a subárvore direita.  Tradicionalmente usam-se 3 tipos de travessias:

 
• PreOrder: pai * esquerda * direita
• InOrder:    esquerda * pai * direita
• PosOrder: esquerda * direita * pai

void preorder (ARV a)
{
  if (! EMPTY(a) )
    { SHOWELEM(a);
      preorder(ESQ(a));
      preorder(DIR(a));
    }
}
 
 
• A função que efectua a travessia inorder recebe a função que "visita" o pai como argumento.

void inorder (ARV a , void (*f)(ELEM e))
{
  if (! EMPTY(a) )
    { inorder(ESQ(a),f);
      (*f)(EL(a));
      inorder(DIR(a),f);
    }
}
 
 

• Uma folha é um nodo que não tem filhos.

 

BOOLEAN folha (ARV n)
{
  return (! EMPTY(n)) && EMPTY(ESQ(n)) && EMPTY(DIR(n));
}
 

• O maior elemento de uma árvore corresponde a descer sempre pela subárvore direita. Quando encontrarmos o nodo com a subárvore direita vazia então esse nodo contém o maior elemento da árvore.

int Max (ARV a)
{
  if (! EMPTY(a))
    { if ( EMPTY(DIR(a)) )
           return EL(a);
      else return Max(DIR(a));
    }
}
 

int Min (ARV a)
{
  if (! EMPTY(a))
    { if ( EMPTY(ESQ(a)) )
           return EL(a);
      else return Min(ESQ(a));
    }
}
 
 

• O peso de uma árvore

int peso(ARV a)
{ int pe, pd;
  if (! EMPTY(a) )
    { pe = peso(ESQ(a));
      pd = peso(DIR(a));
      if (pe > pd)  return(pe+1);
      else          return(pd+1);
    }
  else return(0);
}
 
 

•  Geralmente a funcao de remoção numa estrutura de dados é um pouco mais complicada que os algoritmos de inserção e procura. O caso das árvores binárias de procura  não foge à regra.

Antes de definirmos a função de remoção vamos relembrar duas propriedades da árvore binária de procura:

• O maior elemento da subárvore esquerda  de um nodo n e menor que qualquer elemento da subárvore direita de n.
• O menor elemento da subárvore direita de um nodo n e maior que qualquer elemento da subárvore esquerda de n.
Esta função difere da inserção e da procura quando encontramos o nodo da árvore que contém o elemento que pretendemos remover. Nessa situação temos dois casos:
• Caso I - O nodo a remover é folha: Nesse caso libertamos o nodo e devolvemos a árvore vazia.
• Caso II - O nodo a remover nao é folha: nesse caso podemos substituir o elemento pretendido pelo maior elemento da subárvore esquerda ou pelo menor elemento da subárvore direita.
substituir consiste em copiar o maior (menor) elemento seguido da sua remoção na subárvore esquerda (direita).
 
 
ARV remover (ARV a , ELEM e)
{
  if (! EMPTY(a) )
    { if ( EL(a) == e )
        { if ( folha(a) )
            { free(a);
              return NULL;
            }
          else
            { if EMPTY(ESQ(a))
                { EL(a) = Min(DIR(a));
                  DIR(a) = remover (DIR(a),EL(a));
                  return a;
                }
              else
                { EL(a) = Max(ESQ(a));
                  ESQ(a) = remover (ESQ(a),EL(a));
                  return a;
                }
            }
        }
      else
        { if ( EL(a) < e )
            { DIR(a) = remover (DIR(a),e);
              return a;
            }
          else
            { ESQ(a) = remover (ESQ(a),e);
              return a;
            }
        }
    }
}
 
 

• Aqui podem encontrar a implementação de árvores binárias de procura discutidas nas aulas teorico-praticas. Depois de descomprimir o ficheiro basta fazer make e invocar o programa de teste arv.