Estrutura de Dados

Árvores

Árvores são estruturas de dados organizados através da dependência de elementos sucessores ("filhos") em relação a seus antecessores ("pais"). Existe um componente (nó) especial chamado raiz, a partir do qual a árvore começa. A organização dos nós deve seguir algum critério, sem o que fica difícil empregar a estrutura de forma prática.

Ex.:
Árvore s/ critérios
(apenas conceitual)

Árvores binárias de busca (ABB)

Árvores binárias são estruturas organizadas de forma que cada nó possui zero, um ou dois filhos. Em nenhuma circunstância pode haver violação desta regra. Árvores binárias de busca (ABB) possuem uma regra de formação: geralmente, os descendentes maiores devem ser alocados à direita de seus ascendentes, enquanto os descendentes menores devem ficar à esquerda.

Ex. ABB:

Ex. 2: montagem de uma ABB dada uma certa ordem.

62 - 48 - 84 - 37 - 53 - 96 - 77 -
25 - 40 - 89 - 99 - 65 - 43 - 30 -
50 - 19 - 1

Estrutura de um nó em C

typedef struct temp
{
int dado;
struct temp *dir;
struct temp *esq;
}ABB;

Por exemplo, pode-se declarar alguns ponteiros globais:
ABB *novo, *aux, *pai, *apaga, *raiz;

main()
{
novo = aux = pai = apaga = raiz = NULL;
.
.
.

Inclusão em ABB

void incluir()

{
    int qual;
    printf("nElemento a incluir= "); scanf("%d", qual);
    novo = (ABB*) malloc (sizeof(ABB)); novo -> dado = qual;
    novo -> esq = novo -> dir = NULL;
    if (raiz == NULL) // árvore vazia!
    {
        raiz = novo;
        return;
    }

    posiciona();
    if (novo -> dado > pai -> dado) pai -> dir = novo;
    else pai -> esq = novo;

}


void posiciona()
{
­ aux = pai = raiz;
    while (aux != NULL)
    {
        pai = aux;
        if (novo -> dado > aux -> dado) aux = aux -> dir;
        else aux = aux -> esq;
    }
}

Exclusão em ABB

Pela direita do nó: pegar o menor dos maiores
· Se o sucessor imediato não tiver filhos à esquerda, então
  ele mesmo é o menor dos maiores;
· Se o sucessor imediato tem filhos à esquerda, o menor dos
  maiores é o último elemento à esquerda.

Pela esquerda do nó: pegar o maior dos maiores
  A lógica é a mesma, invertendo os sentidos.

void excluir()
{
    int qual; apaga = raiz;  if (raiz == NULL) return;
    printf("nQual elemento exclui?= "); scanf("%d", &qual);
    while (qual != apaga -> dado && apaga != NULL)
    {
        pai = apaga;
        if (qual > apaga -> dado) apaga = apaga -> dir;
        else apaga = apaga -> esq;
    }
    if (apaga == NULL) return;
    if (apaga -> dir != NULL) excluir_a_direita();
    else excluir_a_esquerda();
}

void excluir_a_direita()
{
    pai = aux = apaga = dir;
    if (aux -> esq == NULL)
    {
        apaga -> dir = aux -> dir;
        apaga -> dado = aux -> dado;
        free(aux);
    }
    while (aux -> esq != NULL)
    {
        pai = aux;
        aux = aux -> esq;
    }
    apaga -> dado = aux -> dado;
    pai -> esq = aux -> dir;
    free (aux);
}

void excluir_a_esquerda()
{
onde for dir (direita) troca por esq (esquerda)
e vice-versa
}