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