Programar em C/Árvores binárias

Origem: Wikilivros, livros abertos por um mundo aberto.

Tabela de conteúdo

[editar] Arvore binária

Uma arvore binária é uma estrutura de dados que pode ser representada como uma hierarquia onde cada elemento é chamado de nó . O nó inicial ou o primeiro elemento é chamado de raiz. Em uma arvore binária um elemento pode ter um máximo de dois filhos no nível inferior denominados como sub-árvore esquerda e sub-árvore direita.Um nó sem filhos é chamado de folha . A profundidade de um nó é a distância deste nó até a raiz e a distancia entre a folha mais distante e a raiz é a altura da arvore.Um conjunto de nós com a mesma profundidade é denominado, nível da árvore.

[editar] Struct

struct No{
    int numero;
    struct No *pEsquerda;
    struct No *pDireita;
};

[editar] Iniciar

void criarArvore(struct No **pRaiz){
    *pRaiz = NULL;
}

[editar] Inserção

void inserir(struct No **pRaiz, int numero){
    if(*pRaiz == NULL){
        *pRaiz = (struct No *) malloc(sizeof(struct No));
        (*pRaiz)->pEsquerda = NULL;
        (*pRaiz)->pDireita = NULL;
        (*pRaiz)->numero = numero;
    }else{
        if(numero < (*pRaiz)->numero)
            inserir(&(*pRaiz)->pEsquerda, numero);
        if(numero > (*pRaiz)->numero)
            inserir(&(*pRaiz)->pDireita, numero);
    }
}

[editar] Remoção

void remover(struct No **pRaiz, int numero){
    struct No *pAux = NULL;
    if(numero < (*pRaiz)->numero)
        remover(&(*pRaiz)->pEsquerda, numero);
    else if (numero > (*pRaiz)->numero)
        remover(&(*pRaiz)->pDireita, numero);
    else{
        pAux = *pRaiz;
        if((*pRaiz)->pEsquerdo == NULL)
            *pRaiz = (*pRaiz)->pDireito;
        else if((*pRaiz)->pDireito == NULL)
            *pRaiz = (*pRaiz)->pEsquerdo;
        else{
            noMaior(&(*pRaiz)->pEsquerda);
            (*pRaiz)->numero = pAux->numero;  
        }
    }
}

[editar] Exibição

[editar] Em ordem

void exibirEmOrdem(struct No *pRaiz){
    if(pRaiz != NULL){
        exibirEmOrdem(pRaiz->pEsquerda);
        printf("\n%i", pRaiz->numero);
        exibirEmOrdem(pRaiz->pDireita);
    }
}

[editar] Pré-ordem

void exibirPreOrdem(struct No *pRaiz){
    if(pRaiz != NULL){
        printf("\n%i", pRaiz->numero);
        exibirPreOrdem(pRaiz->pEsquerda);
        exibirPreOrdem(pRaiz->pDireita);
    }
}

[editar] Pós-ordem

void exibirPosOrdem(struct No *pRaiz){
    if(pRaiz != NULL){
        exibirPosOrdem(pRaiz->pEsquerda);
        exibirPosOrdem(pRaiz->pDireita);
        printf("\n%i", pRaiz->numero);
    }
}

[editar] Contar nós

int contarNos(struct No *pRaiz){
   if(pRaiz == NULL)
        return 0;
   else
        return 1 + contarNos(pRaiz->pEsquerda) + contarNos(pRaiz->pDireita);
}

[editar] Contar folhas

int contarFolhas(struct No *pRaiz){
   if(pRaiz == NULL)
        return 0;
   if(pRaiz->pEsquerda == NULL && pRaiz->pDireita == NULL)
        return 1;
   return 0 + contarFolhas(pRaiz->pEsquerda) + contarFolhas(pRaiz->pDireita);
}

[editar] Altura da árvore

int maior(int a, int b){
    if(a > b)
        return a;
    else
        return b;
}

int altura(struct No *pRaiz){
   if((pRaiz == NULL) || (pRaiz->pEsquerda == NULL && pRaiz->pDireita == NULL))
       return 0;
   else
       return 1 + maior(altura(pRaiz->pEsquerda), altura(pRaiz->pDireita));
}
Obtido em "http://pt.wikibooks.org/wiki/Programar_em_C/%C3%81rvores_bin%C3%A1rias"