Árvore

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define FOLHA       (Folha)malloc(sizeof(struct folha))
#define CMDSTR      500

typedef struct folha* Folha;

struct folha {
    int info;

    Folha   esquerda;
    Folha   direita;
};

Folha inserir (Folha, int), deletar (Folha, int), procurar (Folha, int);
void imprimir_arvore (Folha, int);
void ordenada(Folha), preordenada(Folha), posordenada(Folha);
void cmd (void), help (void);

/* @ Folha inserir (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *  raiz    ponteiro para 'struct folha', estrutura de dado básica para
 *      construção da árvore
 *  info    nova informação a ser inserida
 *
 * Retorno
 * -------
 *  NULL    em caso de erro
 *  Folha   em caso de sucesso (nó 'raiz')
 */
Folha inserir (Folha raiz, int info)
{
    if (!raiz) {
        /* significa que o ponteiro é nulo, e que está é a posição
         * para inserção.
         *
         * 1. Alocar e checar memória
         */
        if (!(raiz = FOLHA)) {
            perror("inserir:malloc()");
            return NULL;
        }

        /* 2. Cópia da Informação
         * 3. Ponteiros de referência
         * 4. Retorno da nova folha
         */
        raiz->info = info;
        raiz->esquerda = raiz->direita = NULL;

        return raiz;
    } else if (info > raiz->info)
        raiz->direita = inserir (raiz->direita, info);
    else
        raiz->esquerda = inserir (raiz->esquerda, info);

    /* retorna o ponteiro raiz
     *
     * Isso é necessário pois a função inserir é recursiva, e seu retorno
     * é sempre atribuido ao mesmo ponteiro passado como argumento 'raiz',
     *
     * raiz->esquerda = inserir(raiz->esquerda,info)
     * raiz->direita  = inserir(raiz->direta,  info)
     */
    return raiz;
}

/* @ Folha deletar (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *  raiz    raiz principal da arvore
 *  info    informação procurada para deletar
 *
 *  Retorno
 *  -------
 *  raiz    em ambos os casos
 */
Folha deletar (Folha raiz, int info) {
    /* para deletar um nó, é necessário que esse nó exista.
     * Então, vamos procurar pelo nó.
     *
     * A remoção de folhas em uma árvore é um pouco mais detalhada que sua
     * similar para listas encadeadas.
     *
     * Existem alguns pontos a se considerar para remover uma folha:
     *  1. A folha é também uma raiz (contém subárvores)?
     *  2.
     */
    Folha filho, n_raiz;

    /* se chegou ao final da arvore e nao encontrou nada para deletar....
     */
    if (!raiz) return NULL;

    /* primeira comparação do programa:
     *  Achamos a informação procurada?
     */
    if (raiz->info == info) {
        /* 1. Existe uma raiz direita?
         *  (uma raiz direita contém todos os elementos MAIORES que
         *  a raiz que estamos excluindo).
         *
         * 2. Caso ela exista, ela será a nova raiz.
         * 3. Os atuais elementos *menores* deverão ser anexados nos
         *    menores elementos da nova raiz (segundo passo).
         */
        if (raiz->direita) {
            /* 2. a nova raiz é a subárvore da direita, que contem
             * todos os elementos MAIORES que a raiz a ser removida
             */
            n_raiz = filho = raiz->direita;

            /* 3. a subárvore esquerda da nova raíz é percorrida
             * até onde não houverem mais elementos. Isso nos dará
             * o menor elemento maior que a folha esquerda de nossa
             * raiz a ser removida.
             */
            while(filho->esquerda)
                filho = filho->esquerda;

            /* o menor elemento maior que a raiz
             * torna-se
             * raiz de todos os elementos menores que a raiz
             * removida
             */
            filho->esquerda = raiz->esquerda;

            /* libera a memória do ponteiro */
            free (raiz);

            /* 1 + 2: nova raiz */
            return n_raiz;

        } else {
            /* caso não haja uma raiz direita (elementos MAIORES)
             * que nossa raiz, a nova raiz da árvore seja o único
             * elemento restante: a subárvore esquerda da árvore,
             * ou os antigos elementos menores que a raiz removida.
             */
            n_raiz = raiz->esquerda;

            /* libera a memória do ponteiro */
            free (raiz);

            /* retorno da nova raiz */
            return n_raiz;
        }

    } else if (info > raiz->info) {
        /* Caso a informação procurada seja maior que a informação na
         * raiz, devemos então procurar pela informação na subárvore
         * da direita (esta operação deverá ser congruente em todo o
         * seu programa.
         *
         * Você não pode ordenar a inserção de um jeito e a remoção de
         * outro!
         */
        raiz->direita = deletar(raiz->direita, info);
    } else {
        /* Caso a informação seja menor que a raiz, procuraremos por ela
         * nas subárvores da esquerda.
         */
        raiz->esquerda = deletar(raiz->esquerda, info);
    }
    /* Lembre-se que as árvores binárias são estruturas de dados recursivas,
     * e por esse motivo, é sempre bom saber o que se está retornando.
     *
     * Assim como na função de inserção, as chamadas recursivas à deletar()
     * esperam como retorno uma raíz! Para onde a raiz->esquerda vai
     * apontar quando a função retornar?
     *
     *  1. Se ela não for excluida, vai ser a própria raiz->esquerda
     *  2. Caso seja excluída, será determinada pelo algoritmo no bloco
     *     if(raiz->info == info).
     *
     * Aqui, no final do escopo da função, significa que é um retorno de
     * chamadas recursivas à deletar (já que o bloco raiz->info == info)
     * retorna por si só. Já que este é um retorno das chamadas recursivas,
     * deve retornar a raiz na qual foi chamada.
     */
    return raiz;
}

Folha procurar (Folha raiz, int info)
{
    /* como todas as funções relativas a arvores binárias são recursivas,
     * todas necessitam de um parametro de "parada de recursão", então,
     * sempre que acharmos um nó NULO, retornamos (até porque não dá pra
     * imprimir informações de um nó que não existe.
     */
    if (!raiz) return NULL;

    if (info > raiz->info) return procurar(raiz->direita, info);
    else return procurar (raiz->esquerda, info);

    /* falhas, compilação, etc */
    return NULL;
}

void imprimir_arvore (Folha raiz, int level)
{
    register int i;

    /* como todas as funções relativas a arvores binárias são recursivas,
     * todas necessitam de um parametro de "parada de recursão", então,
     * sempre que acharmos um nó NULO, retornamos (até porque não dá pra
     * imprimir informações de um nó que não existe.
     */
    if (!raiz) return ;

    /* essa função é uma derivação da ordenação 'inorder', onde primeiro
     * a arvore é percorrida até seu elemento mais esquerdo, e então é
     * impressa a informação da raiz, e então é percorrida suas subárvores
     * direitas.
     *
     * para imprimir de forma 'didática', essa função viaja primeiro pelas
     * folhas direitas, imprime a raiz e então percorre as subárvores
     * esquerdas.
     */
    imprimir_arvore (raiz->direita, level + 1);

    for (i = 0; i < level * 2; i++ ) putchar(' ');
    printf("%d
", raiz->info);

    imprimir_arvore (raiz->esquerda, level + 1);
}

/* @ void ordenada (Folha raiz)
 *
 * Transversalização Ordenada
 * --------------------------
 * Primeiro é visitada a subárvore esquerda, depois a raiz e por último a
 * subárvore direita.
 */
void ordenada (Folha raiz)
{
    if (!raiz) return ;

    ordenada (raiz->esquerda);
    printf ("%d ", raiz->info);
    ordenada (raiz->direita);
}

/* @ void preordenada (Folha raiz)
 *
 * Transversalização Pré-Ordenada
 * ------------------------------
 * Primeiro é visitada a raiz, depois a subárvore esquerda e por último a
 * subárvore direita.
 */
void preordenada (Folha raiz)
{
    if (!raiz) return ;

    printf ("%d ", raiz->info);
    preordenada (raiz->esquerda);
    preordenada (raiz->direita);
}

/* @ void posordenada (Folha raiz)
 *
 * Transversalização Pós-Ordenada
 * ------------------------------
 * Primeiro é visitada a subárvore esquerda, depois a subárvore direita e por
 * último a raiz.
 */
void posordenada (Folha raiz)
{
    if (!raiz) return;

    posordenada (raiz->esquerda);
    posordenada (raiz->direita);
    printf ("%d ", raiz->info);
}

/******************************************************************************
 * Aqui termina todo o código relacionado às árvores binárias e começa o código
 * relative à interface.
 *
 */
void cmd (void)
{
    char cmd[CMDSTR], *arg;
    Folha raiz = NULL;

    help();

    while (1) {
        printf ("ArvoreBinaria> ");
        fgets (cmd, CMDSTR, stdin);

        if (!cmd) continue;

        switch (*cmd) {
        case 'i':
            arg = &cmd[2];
            arg = strtok(arg, " ");
            while (arg) {
                if (!raiz) raiz = inserir (raiz, atoi(arg));
                else inserir (raiz, atoi(arg));

                arg = strtok (NULL, " ");
            }
            break;
        case 'd':
            arg = &cmd[2];
            arg = strtok(arg, " ");
            while (arg) {
                raiz = deletar (raiz, atoi(arg));

                arg = strtok (NULL, " ");
            }
            break;
        case 'm':
            imprimir_arvore (raiz, 0);
            break;
        case 'o':
            ordenada(raiz);
            puts("");
            break;
        case 'r':
            preordenada(raiz);
            puts("");
            break;
        case 'p':
            posordenada(raiz);
            puts("");
            break;
        case 's':
            exit(0);
        case 'h':
            help();
            break;
        default:
            printf("Comando nao reconhecido.
");
            break;
        }

        memset (cmd, 0x0, CMDSTR);
    }
}

/* @ void help (void)
 *
*   i 20    vai inserir o elemento 20 na árvore
 *  d 20    vai remover o elemento 20 da árvore
 *  m   vai mostrar a árvore na tela
 *  o   transversalização ordenada
 *  r   transversalização pré-ordenada
 *  p   transversalização pós-ordenada
 *  s   sai do programa
 *  h   mostra a ajuda
 */
void help (void)
{
    printf ("    |    Arvores Binarias
");
    printf ("    |    Implementacao em C para o Viva O Linux
");
    printf ("    |
");
    printf ("    |    Autor: Enzo Ferber
");
    printf ("    |    2015
");
    printf ("    |

");

    printf ("       Lista de comandos
");
    printf ("       -----------------
");
    printf ("       i %%d - Inserir um elemento
");
    printf ("       d %%d - Deletar um elemento
");
    printf ("       m    - Mostrar a arvore lateralmente
");
    printf ("       o    - Transversalizacao Ordenada
");
    printf ("       r    - Transversalizacao Pre-Ordenada
");
    printf ("       p    - Transversalizacao Pos-Ordenada
");
    printf ("       s    - Sair do programa
");
    printf ("       h    - Mostra a ajuda

");
}

int main (void)
{
    cmd ();
    return 0;
}