Código de árvore binária

Olá, pessoal.

Como prometido, aqui está o código da árvore binária de busca. Lembrem-se: implementem o balanceamento (Árvore AVL) e entreguem até o dia 21/04/15 via e-mail.

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

/* Estrutura de um nó */
struct no
{
    int chave;
    struct no *p;
    struct no *e;
    struct no *d;
};

/* Calcula a altura de uma árvore */
int altura(struct no *raiz)
{
    if(raiz == NULL)
        return 0;

    int e = altura(raiz->e);
    int d = altura(raiz->d);
    int m;

    if (e > d)
        m = e;
    else
        m = d;

    return m + 1;
}

/* Calcula o fator de balanceamento de um nó */
int balanceamento(struct no *raiz)
{
    return altura(raiz->d) - altura(raiz->e);
}

/* Cria um nó */
struct no *criar(int chave)
{
    struct no *novo = malloc(sizeof(struct no));
    novo->chave = chave;
    novo->p = novo->e = novo->d = NULL;
}

/* Busca um nó na árvore */
struct no *buscar(struct no *raiz, int chave)
{
    if(raiz == NULL)
        return NULL;
    if(raiz->chave == chave)
        return raiz;

    if(chave > raiz->chave)
        return buscar(raiz->d,chave);
    else
        return buscar(raiz->e,chave);
}

/* Adiciona elemento na árvore */
struct no *adicionar(struct no *raiz, int chave)
{
    if (raiz == NULL)
    {
        struct no *novo = criar(chave);
        return novo;
    }

    if (chave < raiz->chave)
    {
        struct no *novo = adicionar(raiz->e, chave);
        raiz->e = novo;
        novo->p = raiz;
    }
    else
    {
        struct no *novo = adicionar(raiz->d, chave);
        raiz->d = novo;
        novo->p = raiz;
    }

    return raiz;
}

/* Imprime a árvore em ordem */
void emordem(struct no *raiz)
{
    if (raiz == NULL)
        return;

    emordem(raiz->e);
    printf("%d ",raiz->chave);
    emordem(raiz->d);
}

/* Imprime a árvore em pré-ordem */
void preordem(struct no *raiz)
{
    if (raiz == NULL)
        return;

    printf("%d ",raiz->chave);
    preordem(raiz->e);
    preordem(raiz->d);
}

/* Imprime a árvore em pós-ordem */
void posordem(struct no *raiz)
{
    if (raiz == NULL)
        return;

    posordem(raiz->e);
    posordem(raiz->d);
    printf("%d ",raiz->chave);
}

/* Retorna o mínimo de uma árvore */
struct no *minimo(struct no *raiz)
{
    if (raiz == NULL)
        return;

    if (raiz->e == NULL)
        return raiz;

    return minimo(raiz->e);
}

/* Retorna o máximo de uma árvore */
struct no *maximo(struct no *raiz)
{
    if (raiz == NULL)
        return;

    if (raiz->d == NULL)
        return raiz;

    return maximo(raiz->d);
}

/* Retorna o antecessor de um nó */
struct no *antecessor(struct no *raiz)
{
    if(raiz->e == NULL)
    {
        while(raiz->p != NULL && raiz->p->chave > raiz->chave  )
            raiz = raiz->p;

        return raiz->p;
    }
    return maximo(raiz->e);
}

/* Retorna o sucessor de um nó */
struct no *sucessor(struct no *raiz)
{
    if(raiz->d == NULL)
    {
        while(raiz->p != NULL && raiz->p->chave < raiz->chave  )
            raiz = raiz->p;
        return raiz->p;
    }

    return minimo(raiz->d);

}

/* Remove um nó da árvore e retorna a nova árvore */
struct no* remover(struct no *arvore, int chave)
{
    if(arvore == NULL)
        return NULL;

    struct no *raiz = buscar(arvore, chave);

    if (raiz == NULL)
        return arvore;

    // Remover NO sem Filhos
    if (raiz->e == NULL && raiz->d == NULL)
    {
        if(raiz->p != NULL)
        {
            if(raiz->p->chave >= raiz->chave)
                raiz->p->e = NULL;
            else
                raiz->p->d = NULL;
            free(raiz);
        }
        else
        {
            free(raiz);
            return NULL;
        }
        if (raiz == arvore)
            return NULL;
    }
    else
    {
        // Remover NO com 2 Filhos
        if (raiz->e && raiz->d != NULL)
        {
            struct no *ant = antecessor(raiz);
            raiz->chave = ant->chave;
            ant = remover(ant, ant->chave);
        }
        // Remover NO com 1 Filho
        else
        {
            //Reconectar Filho a Esquerda
            if(raiz->e != NULL)
            {
                if (raiz->p != NULL)
                {
                    if(raiz->p->chave > raiz->chave)//Caso o pai seja maior
                        raiz->p->e = raiz->e;
                    else//Caso o pai seja menor
                        raiz->p->d = raiz->e;
                }
                raiz->e->p = raiz->p;
            }
            //Reconectar Filho a Direita
            else
            {
                if (raiz->p != NULL)
                {
                    if(raiz->p->chave < raiz->chave)//Caso o pai seja menor
                        raiz->p->d = raiz->d;
                    else//Caso o pai seja maior
                        raiz->p->e = raiz->d;
                }
                raiz->d->p = raiz->p;

                free(raiz);
            }
        }
    }

    return arvore;
}

/* Função principal */
int main(void)
{
    struct no *arvore = NULL;
    int opt, chave;

    do
    {
        printf("Escolha uma opcao:\n\n");
        printf("1 - Adicionar\n");
        printf("2 - Listar\n");
        printf("3 - Remover\n");
        printf("0 - Sair\n");
        scanf("%d", &opt);

        switch(opt)
        {
        case 1:
            printf("\n\nDigite uma chave: ");
            scanf("%d", &chave);
            arvore = adicionar(arvore, chave);
            break;

        case 2:
            printf("\n\n");
            printf("Em ordem: \n");
            emordem(arvore);
            printf("\n\n");
            printf("Pre ordem: \n");
            preordem(arvore);
            printf("\n\n");
            printf("Pos ordem: \n");
            posordem(arvore);
            printf("\n\n");
            break;

        case 3:
            printf("\n\nDigite a chave a ser removida: ");
            scanf("%d", &chave);
            arvore = remover(arvore, chave);
            break;

        case 0:
            return 0;

        default:
            printf("Opcao invalida!\n\n");
        }
    }
    while(1);

    return 0;
}