Doubts in Binary Tree in C - Print order, preorder and post order

5

I have several doubts about how binary tree work in C.

I have an insertion, removal and printing code in order, pre-order and post-order. These codes were taken from the internet, because I could not understand what each line does following the explanations of my teacher.

Struct

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

First Question

In this case I created a struct No and I created 2 pointers of type Not being left and right, correct?

Tree Creation

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

2nd Doubt

In this code I created the tree, but what does **pRaiz mean?

3rd Doubt

If you have someone on time, can you tell me what's going on in each line of the code insert below?

4th Doubt

If you have someone on time, can you tell me what's going on in each line of removal of the code below?

Insertion

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);
    }
}

Removal

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;   
                   }
                }
             }
          }
}

Order Printing

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

Pre-order printing

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

Post-order printing

void exibirPosOrdem(No *pRaiz){
    if(pRaiz != NULL){
        exibirPosOrdem(pRaiz->esquerda);
        exibirPosOrdem(pRaiz->direita);
        printf("\n%i", pRaiz->numero);
    }
}
    
asked by anonymous 26.03.2017 / 22:09

1 answer

2

1st Doubt - Exactly, it will be the two children.

2nd Doubt - ** pRaiz will be the Node you will create to be the ROOT. Since it is a pointer that will POINT to another pointer, which is the root of the tree, two asterisks must be used, "**".

3rd Doubt

Insertion

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);
    }
}

What may end up causing confusion in this code is the name of the signature node of the **pRaiz function. Not a good name, in my opinion, could only be used no , or noAtual . It causes a confusion, it seems that you are always accessing the Root, which is not true.

Removal

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
                       }
                    }
                 }
              }
    }

Order Printing

//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
        }
    }

Pre-order Printing

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
    }
}

Post-order printing

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);
    }
}
    
27.03.2017 / 00:24