Segue abaixo o código fonte de cada arquivo separado.
ABB_privado.h
/*Árvore Binária de Busca - ABB*/
/*ABB_privado*/
#ifndef ABB_PRIVADO_H
#define ABB_PRIVADO_H
#include "ABB_interface.h"
typedef struct noABB
{
    struct noABB *dir;
    struct noABB *esq;
    void *dados;
}NoABB,*pNoABB;

typedef struct ABB
{
    int tamInfo;
    pNoABB raiz;
}ABB;

int auxReinicia(pNoABB p);
#endif  

ABB_interface.h
/*ABB_interface.h*/
#ifndef ABB_INTERFACE_H
#define ABB_INTERFACE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SUCESSO 1
#define FRACASSO 0
#define MAIOR 1
#define MENOR -1
#define IGUAL 0
#define SIM 1
#define NAO 0

typedef struct ABB *pABB,**ppABB;

int criaABB(ppABB pp,int tamInfo);
int insereABB(pABB p,void *novo,int(*comparaElemElem)(void *k,void *e));
int removeABB(pABB p,void *chave,int (*comparaChaveElem)(void *e1,void *e2));
int buscaABB(pABB p,void *chave,void *destino,int (*comparaChaveElem)(void *e1,void *e2));
/*int percurso_em_ordem(pABB p,void(*visita)(void *info));
int percurso_pre_ordem(pABB p,void(*visita)(void *info));
int percurso_pos_ordem(pABB p,void(*visita)(void *info));*/
int testaVaziaABB(pABB p);
void reiniciaABB(pABB p);

void destroiABB(ppABB pp);
#endif

ABB.c
#include "ABB_privado.h"
/******************************************************************************************/
int criaABB(ppABB pp,int tamInfo)
{
    (*pp) = (pABB )malloc(sizeof(ABB));
    if((*pp) == NULL)
     return FRACASSO;
    (*pp)->tamInfo = tamInfo;
    (*pp)->raiz = NULL;
    return SUCESSO;
}
/*******************************************************************************************/
int buscaABB(pABB p,void *chave,void *destino,int(*comparaChaveElem)(void *k,void *e))
{
    pNoABB aux;
    if(p == NULL) /*se a árvore não foi criada*/
     return FRACASSO;
     if(testaVaziaABB(p) == SIM) /*se a árvore estiver vazia*/
       return FRACASSO;
       aux = p->raiz;
       while(aux != NULL && comparaChaveElem(chave,aux->dados) != IGUAL)
       {
           if(comparaChaveElem(chave,aux->dados) == MENOR)
           {
               aux = aux->esq;
           }
           else aux = aux->dir;
       }
       if(aux == NULL) /*não encontrado*/
       return FRACASSO;
       memcpy(destino,aux->dados,p->tamInfo);
       return SUCESSO;
}
/********************************************************************************************/
int insereABB(pABB p,void *novo,int(*comparaElemElem)(void *e1,void *e2))
{
    pNoABB aux = NULL, ant = NULL;
    if(p == NULL) /*se a árvore não foi criada*/
     return FRACASSO;
    aux = p->raiz;
    while(aux != NULL)
    {
        ant = aux;
        if(comparaElemElem(novo,aux->dados) == MENOR)
            aux = aux->esq;
        else if(comparaElemElem(novo,aux->dados) == MAIOR)  
            aux = aux->dir;
        else if(comparaElemElem(novo,aux->dados) == IGUAL)
        {
            printf("\n!!!ERRO!!!Chave igual\n");
            return FRACASSO;
        }    
    }
     aux = (pNoABB )malloc(sizeof(NoABB));
     if(aux == NULL) return FRACASSO;
     aux->dados = malloc(p->tamInfo);
     if(aux->dados == NULL)
     {
         free(aux);  aux = NULL;
         return FRACASSO;
     }
     memcpy(aux->dados,novo,p->tamInfo);
     aux->dir = NULL;
     aux->esq = NULL;
      if(ant != NULL) /*se for inserir a folha da árvore*/
      {
          if(comparaElemElem(novo,ant->dados) == MENOR)
            ant->esq = aux;
          else if(comparaElemElem(novo,ant->dados) == MAIOR)
            ant->dir = aux;
          return SUCESSO;
      }    
      if(ant == NULL) /*árvore vazia*/
      {
           p->raiz = aux;
           return SUCESSO;
      }
  return SUCESSO;
}
/******************************************************************************************/
int removeABB(pABB p,void *chave,int(*comparaChaveElem)(void *k,void *e))
{
    /*Remoção:
    casos:
    1) Remoção de um nó sem filhos
    2) Remoção de um nó com um único filho(esquerdo ou direito)
    3) Remoção de um nó com dois filhos substituído pelo nó Sucessor(ou Antecessor) vem
       vem na sequência da ordenação.
    */
    pNoABB aux,ant,suc,pai_suc,x;
    ant = NULL;
    if(p == NULL) /*se a árvore não foi criada*/
      return FRACASSO;
      if(testaVaziaABB(p) == SIM) /*se a árvore estiver vazia*/
         return FRACASSO;
         aux = p->raiz;
         while(aux != NULL && comparaChaveElem(chave,aux->dados) != IGUAL)
         {
             ant = aux;
             if(comparaChaveElem(chave,aux->dados) == MENOR)
                aux = aux->esq;
                else  aux = aux->dir;
         }
         if(aux == NULL) /*não encontrou*/
            return FRACASSO;
            if(aux->esq == NULL && aux ->dir == NULL) /*caso 1*/
            {
                if(ant == NULL)
                  p->raiz = NULL;
                  else
                  {
                      if(comparaChaveElem(chave,ant->dados) == MENOR)
                      {
                        ant->esq = NULL;
                      }
                      else  ant->dir = NULL;
                  }
            }
            else if(aux->esq == NULL || aux->dir == NULL) /*caso 2*/
            {
                if(ant == NULL) /*remoção da raiz*/
                {
                    if(aux->esq == NULL)
                       p->raiz = aux->dir;
                    else   p->raiz = aux->esq;
                }
                else
                {
                    if(aux->esq == NULL)
                       x = aux->dir;
                    else  x = aux->esq;
                    if(ant->esq == aux)
                       ant->esq = x;
                    else ant->dir = x;
                }
            }
            else /*caso 3*/
            {
                suc = aux->dir;
                pai_suc = aux;
                while(suc->esq != NULL)
                {
                    pai_suc = suc;
                    suc = suc->esq;
                }
                pai_suc->esq = suc->dir;
                suc->esq = aux->esq;
                suc->dir = aux->dir;
                if(ant == NULL) /*remoção da raiz com dois filhos*/
                {
                    p->raiz = suc;
                }
                else
                {
                  if(ant->esq == aux)
                    ant->esq = suc;
                    else  ant->dir = suc;
                }
            }
            free(aux->dados);
            free(aux);
            return SUCESSO;
}
/******************************************************************************************/
int testaVaziaABB(pABB p)
{
    if(p->raiz == NULL)
     return SIM;
     else
      return NAO;
}
/******************************************************************************************/    
void reiniciaABB(pABB p)
{
    auxReinicia(p->raiz);
    p->raiz = NULL;
}
/******************************************************************************************/
int auxReinicia(pNoABB p)
{
    if(p != NULL)
    {
        auxReinicia(p->esq);
        auxReinicia(p->dir);
        free(p->dados);
        free(p);
    }
    else
    return FRACASSO;
}
/******************************************************************************************/
void destroiABB(ppABB pp)
{
    reiniciaABB(*pp);
    free(*pp);
    *pp = NULL;
}        

ABB_Aplica.h                    
/*ABB_Aplicação.h*/
#ifndef ABB_APLICA_H
#define ABB_APLICA_H
#include "ABB_interface.h"
typedef struct info{
    long chave;
    char nome[40];
    char fone[15];
    float salario;
    }Info;  
    
int comparaElemElem(void *e1,void *e2);
int comparaChaveElem(void *k,void *e);
#endif

ABB_Aplica.c
/*******************************************************************************
    Universidade do Estado de Santa Catarina - UDESC
       Centro de Ciências Tecnológicas - CCT
          Bacharelado em Ciência da Computação - BCC
             Acadêmico: Reginaldo de Matias
                E-mail: reginaldo.matias@gmail.com
********************************************************************************/
#include "ABB_Aplica.h"
int comparaElemElem(void *e1,void *e2)
{
    long *c = (long *)e1;
    Info *i = (Info *)e2;
    if(*c > i->chave)
      return MAIOR;
    else if(*c  < i->chave)
       return MENOR;
       else
         return IGUAL;
}      
int comparaChaveElem(void *e1,void *e2)
{
    Info *x1 = (Info *)e1;
    Info *x2 = (Info *)e2;
    if(x1->chave > x2->chave)
      return MAIOR;
    else if(x1->chave < x2->chave)
       return MENOR;
       else
         return IGUAL;
}
int main()
{
    pABB p = NULL;
    Info reg;
    int op,id;
    if(criaABB(&p,sizeof(Info)) == SUCESSO)
    {
        do{
            system("title Árvore Binária de Busca :. ABB");
            system("color 9A");
        printf("\n\tArvore Binaria de Busca :. ABB\n");
        printf("[1]Inserir\n");
        printf("[2]Remover\n");
        printf("[3]Buscar\n");
        printf("[4]Resetar\n");
        printf("[5]Creditos\n");
        printf("[0]Sair\n");
        scanf("%i",&op);
        switch(op)
        {
            case 1:
                fflush(stdin);
                printf("Numero da chave: ");
                scanf("%li",&(reg.chave));
                fflush(stdin);
                printf("Nome: ");
                gets(reg.nome);
                fflush(stdin);
                printf("Fone: ");
                scanf("%s",&(reg.fone));
                fflush(stdin);
                printf("Salario: ");
                scanf("%f",&(reg.salario));
                fflush(stdin);
                if(insereABB(p,&reg,comparaElemElem) == SUCESSO)
                printf("\nDado Inserido com Sucesso!\n");
                else
                printf("\nChave jah existe\n");
                break;
           case 2:
               if(testaVaziaABB(p) == SIM)
                 printf("\n!!!Arvore Vazia!!!\n");
                 else
                 {
                    printf("Entre com a chave que deseja remover: ");
                    scanf("%i",&id);
                    if(removeABB(p,&id,comparaChaveElem) == SUCESSO)
                       printf("\nDado removido com Sucesso!\n");
                    else
                       printf("\nChave Inexistente!\n");
                 }    
               break;
           case 3:
               if(testaVaziaABB(p) == SIM)
                 printf("\n!!!Arvore Vazia!!!\n");
                 else
                 {
                     printf("Entre com a chave que deseja consultar: ");
                     scanf("%i",&id);
                     if(buscaABB(p,&id,&reg,comparaChaveElem) == SUCESSO)
                     {
                         printf("Chave:. %i\n",reg.chave);
                         printf("Nome:. %s\n",reg.nome);
                         printf("Fone:. %s\n",reg.fone);
                         printf("Salario:. %f\n",reg.salario);  
                     }
                     else
                        printf("\nChave Inexistente!\n");
                 }    
               break;
           case 4:
               if(testaVaziaABB(p) == SIM)
               printf("\nA Arvore jah se encontra Vazia\n");
               else
               {
                   reiniciaABB(p);
                   printf("\nArvore Reiniciada com Sucesso!\n");
               }
               break;
           case 5:
               printf("\n|******************************************************|");
               printf("\n|Academico: Reginaldo de Matias                        |");
               printf("\n|Ciencia da Computacao - UDESC                         |");
               printf("\n|******************************************************|");
               break;
        }
    }while(op != 0);    
     destroiABB(&p);
   }
   else
   {
       printf("\nERRO! NAO FOI POSSIVEL CRIAR A ARVORE!\n");
   }
system("Pause");
}                    
  


OK! Qualquer dúvida entre em contato.