Question:
I have several doubts about how a binary tree works in C.
I have an insert, remove and print code in order, pre-order and post-order. These codes were taken from the internet, because I couldn't understand what each line does 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 type No 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
In case you have someone with time, can you tell me what is happening on each line of the code insertion below?
4th Doubt
In case anyone has time, can you tell me what's happening on each line of the 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;
}
}
}
}
}
Print 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:
1st Doubt – Exactly, it will be the two children.
2nd Doubt – **pRoot` will be the Node that you will 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.
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 can 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 in noAtual . It causes 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
}
}
}
}
}
Print 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);
}
}