Doubts in Arvore Binaria in C - Printing order, pre-order and post-order

Question

I have several doubts about the operation of binary tree in C.

I have a code for insertion, removal and printing in order, pre-order and post-order. These codes were taken from the Internet, because I couldn’t understand what each line does by following my teacher’s explanations.

Struct

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

1st Doubt

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

Creation of the Tree

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

2nd doubt

In this code I created the tree, but what it means **pRaiz?

Third doubt

If you have someone with time, you can tell me what is happening on each line of code insertion below?

4th doubt

If you have someone with time, can you tell me what is happening in each line of code removal 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;   
                   }
                }
             }
          }
}

Printing in Order

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

Answer 1

1st Doubt - That’s right, it’ll be the two children.

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

Third 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 can end up causing confusion in this code is the Node name of the function signature **pRaiz. Not a good name, in my opinion, could be used only no, or noAtual. Cause 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
                       }
                    }
                 }
              }
    }

Printing in Order

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