6

Estou com diversas dúvidas no funcionamento de arvore binária em C.

Tenho um código de inserção, remoção e impressão em ordem, pré-ordem e pós-ordem. Estes códigos foram pegados da internet, pois não consegui entender o que cada linha faz seguindo as explicações do meu professor.

Struct

struct No{
    int numero;
    struct No *esquerda;
    struct No *direita;
};
typedef struct No No;

1ª Dúvida

Neste caso eu criei um struct No e criei 2 ponteiros do tipo No sendo eles esquerda e direita, correto?

Criação da Árvore

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

2ª Dúvida

Neste código eu criei a arvore, mas o que significa **pRaiz?

3ª Dúvida

Caso tenha alguém com tempo, pode me dizer o que está acontecendo em cada linha da inserção do código abaixo?

4ª Dúvida

Caso tenha alguém com tempo, pode me dizer o que está acontecendo em cada linha da remoção do código abaixo?

Inserção

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

Remoção

No *MaiorDireita(No **no){
    if((*no)->direita != NULL) 
       return MaiorDireita(&(*no)->direita);
    else{
       No *aux = *no;
       if((*no)->esquerda != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da esquerda!
          *no = (*no)->esquerda;
       else
          *no = NULL;
       return aux;
       }
}

No *MenorEsquerda(No **no){
    if((*no)->esquerda != NULL) 
       return MenorEsquerda(&(*no)->esquerda);
    else{
       No *aux = *no; 
       if((*no)->direita != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da direita!
          *no = (*no)->direita;
       else
          *no = NULL;
       return aux;
       }
}

void remover(No **pRaiz, int numero){
    if(*pRaiz == NULL){   // esta verificacao serve para caso o numero nao exista na arvore.
       printf("Numero nao existe na arvore!");
       getch();
       return;
    }
    if(numero < (*pRaiz)->numero)
       remover(&(*pRaiz)->esquerda, numero);
    else 
       if(numero > (*pRaiz)->numero)
          remover(&(*pRaiz)->direita, numero);
       else{    // se nao eh menor nem maior, logo, eh o numero que estou procurando! :)
          No *pAux = *pRaiz;     // quem programar no Embarcadero vai ter que declarar o pAux no inicio do void! :[
          if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // se nao houver filhos...
                free(pAux);
                (*pRaiz) = NULL; 
               }
          else{     // so tem o filho da direita
             if ((*pRaiz)->esquerda == NULL){
                (*pRaiz) = (*pRaiz)->direita;
                pAux->direita = NULL;
                free(pAux); pAux = NULL;
                }
             else{            //so tem filho da esquerda
                if ((*pRaiz)->direita == NULL){
                    (*pRaiz) = (*pRaiz)->esquerda;
                    pAux->esquerda = NULL;
                    free(pAux); pAux = NULL;
                    }
                else{       //Escolhi fazer o maior filho direito da subarvore esquerda.
                   pAux = MaiorDireita(&(*pRaiz)->esquerda); //se vc quiser usar o Menor da esquerda, so o que mudaria seria isso:
                   pAux->esquerda = (*pRaiz)->esquerda;          //        pAux = MenorEsquerda(&(*pRaiz)->direita);
                   pAux->direita = (*pRaiz)->direita;
                   (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
                   free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   
                   }
                }
             }
          }
}

Impressão em Ordem

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

Impressão Pré-ordem

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

Impressão Pós-ordem

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

1 Resposta 1

3

1ª Dúvida - Exato, serão os dois filhos.

2ª Dúvida - **pRaiz` será o Nó que você irá criar para ser a RAIZ. Como ele é um ponteiro que APONTARÁ para outro ponteiro, que é a raiz da árvore, tem que ser usados dois asteríscos, " ** ".

3ª Dúvida

Inserção

void inserir(No **pRaiz, int numero){// irá recebar a raiz(**pRaiz) e o número a ser inserido. Pois ele irá testar o número a ser inserido desde a raiz até onde ele deverá ficar.
    if(*pRaiz == NULL){//Se *pRaiz for null, ou seja, não existir raiz, ele irá adicionar esse número a raiz.
        *pRaiz = (No *) malloc(sizeof(No));//esse maloc é pra alocar memória de um nó
        (*pRaiz)->esquerda = NULL;
        (*pRaiz)->direita = NULL;//os filhos a esquerda e a direita ainda não existem, por isso, são nulos.
        (*pRaiz)->numero = numero;//inserção do número
    }else{//JÁ EXISTE UMA RAIZ
        if(numero < (*pRaiz)->numero) // testa se o número a ser inserido é menor que o do Nó atual
            inserir(&(*pRaiz)->esquerda, numero);// caso for, ele irá ter que ser inserido à esquerda desse Nó atual, por isso é passado o *pRaiz->esquerda. O '&' é porque ele ta passando só a referência
        if(numero > (*pRaiz)->numero)//Aqui é a mesma situação, só que no caso do número a ser inserido ser maior
            inserir(&(*pRaiz)->direita, numero);
    }
}

O que pode acabar causando uma confusão nesse código é o nome do Nó da assinatura da função **pRaiz. Não é um bom nome, na minha opinião, Poderia ser usado somente no, ou noAtual. Causa uma confusão, parece que você está sempre acessando a Raiz, o que não é verdade.

Remoção

No *MaiorDireita(No **no){    //Essas duas funções, *MaiorDireita e *MenorEsquerda são duas funções auxiliares. Vão ser usadas na hora de remover um Nó que tenha filhos a direita e a esquerda
//essa função vai ser usada pra, como o próprio nome já diz, buscar o Maior nó a direita
//Recebe um No **no que será o nó a ser removido, a partir dai ele busca o maior à direita
        if((*no)->direita != NULL)//caso seja diferente de null, ou seja, existe algum nó à direita, ele chama recursivamente o próximo nó à direita
           return MaiorDireita(&(*no)->direita);
        else{//caso contrário, esse é o maior nó a direita.
           No *aux = *no;//faz um backup do nó, pois ele irá excluir esse nó, e irá adicioná-lo em outro lugar
           if((*no)->esquerda != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da esquerda!
              *no = (*no)->esquerda;
           else
              *no = NULL;
           return aux;
           }
    }

    No *MenorEsquerda(No **no){//Essa função tem a mesma característica da anterior. Dependendo da sua abordagem, você pode usar uma ou outra. Se a sua abordagem é de pegar o Menor à esquerda, use essa função, caso contrário, utilize a anterior.
        if((*no)->esquerda != NULL) 
           return MenorEsquerda(&(*no)->esquerda);
        else{
           No *aux = *no; 
           if((*no)->direita != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da direita!
              *no = (*no)->direita;
           else
              *no = NULL;
           return aux;
           }
    }

    void remover(No **pRaiz, int numero){//Mais uma vez aquela confusão do **pRaiz, mas já está ciente do problema. A função recebe o nó raiz, e um número a ser removido. Irá fazer uma busca de onde está esse número e depois executa a lógica de remoção.
        if(*pRaiz == NULL){   // esta verificacao serve para caso o numero nao exista na arvore.
           printf("Numero nao existe na arvore!");
           getch();
           return;
        }

        if(numero < (*pRaiz)->numero)//verifica se o número é menor que o número do Nó atual, na busca.
           remover(&(*pRaiz)->esquerda, numero);//chamada recursiva para caso seja menor
        else//caso contrário, ele será o número ou será maior 
           if(numero > (*pRaiz)->numero)//verifica se o número é maior que o número do Nó atual, na busca.
              remover(&(*pRaiz)->direita, numero);//chamada recursiva para caso seja maior
           else{    // se nao eh menor nem maior, logo, eh o numero que estou procurando! :)
              No *pAux = *pRaiz;     // faz um backup do Nó a ser removido
              if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // verifica se não tem filho nem a direita, nem a esquerda, ou seja, não tem filhos. 
                    free(pAux);//Nesse Caso, é bem simples, é só desalocar, liberar esse nó da memória
                    (*pRaiz) = NULL; 
                   }
              else{     // so tem o filho da direita
                 if ((*pRaiz)->esquerda == NULL){//Verifica se não tem filho a esquerda, caracterizando como tendo filhos somente a direita.
                    (*pRaiz) = (*pRaiz)->direita;//o Nó atual, recebe o seu filho a direta, fazendo com que ele desapareça e o seu próximo filho substitua o seu lugar
                    pAux->direita = NULL;//o backup se faz necessário para isso, para você cortar essa ligação, caso contrário, teria um nó em memória que teriam os antigos filhos
                    free(pAux); pAux = NULL;// e também para poder liberá-lo da memória depois
                    }
                 else{            //so tem filho da esquerda
                    if ((*pRaiz)->direita == NULL){//MESMO CASO ANTERIOR, só que nesse caso, só existem filhos a esquerda.
                        (*pRaiz) = (*pRaiz)->esquerda;
                        pAux->esquerda = NULL;
                        free(pAux); pAux = NULL;
                        }
                    else{       //Quando existe filhos a direita e a esquerda. Escolhi fazer o maior filho direito da subarvore esquerda.
                       pAux = MaiorDireita(&(*pRaiz)->esquerda); //Faz um backup do Maior a direita, pois ele usará o maior a direita no local do Nó a ser removido. Se vc quiser usar o Menor da esquerda, so o que mudaria seria isso: pAux = MenorEsquerda(&(*pRaiz)->direita);
                       pAux->esquerda = (*pRaiz)->esquerda;          //o Nó(Maior a Direita) irá receber os filhos a esquerda do Nó que será removido        
                       pAux->direita = (*pRaiz)->direita;//o Nó(Maior a Direita) irá receber os filhos a direita do Nó que será removido
                       (*pRaiz)->esquerda = (*pRaiz)->direita = NULL;//O Nó que será removido, perde seus filhos, ou seja, recebe NULL 
                       free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   //Enfim, libera-se da memória o nó a ser removido
                       }
                    }
                 }
              }
    }

Impressão em Ordem

//O em ordem, como você já deve saber, ele busca o último à esquerda, depois volta até o nó onde ele terá que ir à direita. Após isso ele busca o último à esquerda e volta....
    void exibirEmOrdem(No *pRaiz){//recebe o nó raiz, de novo aquela confusão com o nome da variável
        if(pRaiz != NULL){//verifica se o nó atual existe, pois ao ser chamado pRaiz->direita ou pRaiz->esquerda, sabemos que poderão ser nulos
            exibirEmOrdem(pRaiz->esquerda);//chamada recursiva para o próximo à esquerda, e será chamado até o último à esquerda.
            printf("\n%i", pRaiz->numero);//Ao chegar no último à esquerda, ou seja, for pRaiz->esquerda for NULL, ele começa a printar, e vai printando todos os nós por onde ele passou, "voltando"
            exibirEmOrdem(pRaiz->direita);//é chamado o nó a direita, seguindo o fluxo
        }
    }

Impressão Pré-ordem

void exibirPreOrdem(No *pRaiz){//Pré-Ordem é mais simples, no nó que ele tá, ele já printa. Começa pela raiz e vai printando até o último a esquerda, depois volta pro nó onde ele terá que ir até a esquerda e volta denovo a buscar o último a esquerda e segue o fluxo.
    if(pRaiz != NULL){//mesmo teste anterior
        printf("\n%i", pRaiz->numero);//assim que está no nó, já faz o print
        exibirPreOrdem(pRaiz->esquerda);//faz a chamada recursiva pro nó a esquerda, perceba que o pRaiz->direita só é chamado quando passa por todos os nós a esquerda
        exibirPreOrdem(pRaiz->direita);//chamada recursiva para nó à direita
    }
}

Impressão Pós-ordem

void exibirPosOrdem(No *pRaiz){//Pós-ordem é o que eu acho mais complicado, mas não impossível de entender. A ideia basicamente é passar por toda a árvore, e só depois vir fazendo os prints. Ele busca o último a esquerda, depois volta pro nó que tiver que voltar e vai pra direita, sem printar nada, e busca de novo o último a esquerda, ate varrer toda a árvore, depois ele vai printando tudo.
    if(pRaiz != NULL){
        exibirPosOrdem(pRaiz->esquerda);
        exibirPosOrdem(pRaiz->direita);
        printf("\n%i", pRaiz->numero);
    }
}
2
  • 1
    obrigado pela ajuda. Você poderia complementar a resposta comentando a remoção também, tenho dúvidas nesta parte.
    – Wendell
    Commented 26/03/2017 às 22:52
  • 1
    Pronto, terminei de fazer a resposta. Qualquer dúvida, fala ai que a gente tenta sanar. Commented 28/03/2017 às 3:13

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .