Linguagem C: Árvores

Linguagem C: Árvores

ÁRVORES

Árvore, no contexto da programação e ciência da computação, é uma estrutura de dados que herda as características das topologias em árvore. Conceitualmente diferente das listas encadeadas, em que os dados se encontram numa sequência, nas árvores os dados estão dispostos de forma hierárquica. (Wikipédia)

Algumas noções básicas de árvores:
- Nós: (A, B,...)
- Folhas: Nós de grau zero, sem filhos para nenhum dos lados.
-Profundidade de um nó: Nível em que o nó se encontra na árvore.
-Altura: É o tamanho total da profundidade da árvore.


Esta aula visa dar uma visão geral sobre árvores que serão estes os tipos que serão abordados:
 - Árvores binárias
- Árvores binárias de pesquisa (basicamente a mesma árvore binária porém organizada).
- Árvores AVL
___________________________________________________________________

As árvores podem ser percorridas de 3 maneiras distintas:
- pré-ordem: Visita primeiro a raiz depois vai para a sub-arore esquerda e por último para a direita.
- pós-ordem: Visita sub-árvore esquerda, depois a raiz e por último a sub-árvore direita.
-simétrica: Visita a sub-árvore esquerda, depois visita a sub-árvore direita e por última visita a raiz.

A estrutura de uma árvore binária ou binária de pesquisa é a seguinte:

typedef struct _tnode_ {      void *item;      struct tnode *right;      struct tnode *left }tnode;
A seguir os três métodos de percorrer árvores que pode ser utilizado para qualqur tipo de árvore a mesma idéia, lembrando que as árvores utilizam o princípio da recursividade:

void preordem( tonde *t, void visit(void*)){
   if ( t != NULL){
      visit( t->item)
      preordem(t->left,visit);
      preordem(t->right,visit);
   }
}

void simetrica (tnode *t, void visit(void*)){
   if( t != NULL){
       simetrica (t->left,visit);
       visit ( t->data);
       simetrica (t->right,visit);
   }
}

void posordem (tnode *t, void visit(void*)){
    if( t != NULL){
      posordem (t->left,visit);
      posordem(t->right,visit);
      visit(t->data);
    }
}

 Estes 3 métodos de percorrer árvores usam recursividade, ou seja, fazem chamadas a si mesmo para percorrer a árvore guardando o local do nó anterior da árvore.

_____________________________________________________________________



*Árvores binárias:
-São compostos por nós.

-Duas sub-árvores no máximo (Left e Right).

-As duas sub-árvores são binárias.
A característica principal de uma árvore binária de pesquisa é que, para qualquer nó da árvore, o valor dos nós na sub-árvore esquerda é menor ou igual ao valor da raiz, e para qualquer valor dos nós da sub-árvore direita é mais ou igual ao valor da raiz.

Existem ainda dois tipos de árvores binárias de pesquisa:
-Árvore binária completa: É toda árvore na qual todas os níveis estão preenchidos.
-Árvore binária completa de n nós: É toda árvore na qual todos os níveis estão preenchidos, exceto o útimo.

Para sabermos qual a altura de uma árvore binária comleta de altura h, basta utilizarmos a fórmula de:
nós = log2 (n+1)/2. (para n igual a quantidade total de nós da árvore).

Para sabermos se uma árvore binária é balanceada a altura da subárvore esquerda menos a altura da direita tem que ser menor ou igual a 1 para todo nó (He - Hd <= 1).