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