Hello, I need to make the function verify AVL (which is called in case 8, line 364) , check whether the tree is AVL or not , that is, if the result of their nodes are -1,0 or 1, it just writes on the screen: INSERTED TREE IS AVL, if it finds any node value DIFFERENT from those quoted, return: NOT AVL.
The function starts at line 276, at line 260 and 246 you will see that I tried to implement another function that would check for each side of the tree and then returns to check the VLL its degree, without success. (will be commented incomplete where it needs to be implemented ...)
I have tried here, because I am days on it, I have already done (as you can see in the code) check if the tree is pre-fixed, if it is postfixed or central walking with great difficulty since I am new to C and especially in the issue of implementing the recursive code I'm trying, there is no coffee that arrives any more, I'm desperate, I ask for help.
#include <stdio.h>
#include <stdlib.h>
struct Vertice
{
int chave;
struct Vertice* esquerdo;
struct Vertice* direito;
};
int menu()
{
int op;
printf("(1)Inserir\n");
printf("(2)Imprimir\n");
printf("(3)Excluir folha\n");
printf("(4)Procurar chave\n");
printf("(5)Executar caminhamento pre-fixado\n");
printf("(6)Executar caminhamento pos-fixado\n");
printf("(7)Executar caminhamento central\n");
printf("(8)Verificar se a arvore e AVL\n");
printf("(9)Sair\n");
printf("Digite uma opcao: ");
scanf("%d",&op);
return op;
}
struct Vertice* alocaVertice(int chave)
{
struct Vertice* novo;
novo = (struct Vertice*)malloc(sizeof(struct Vertice));/*aloca memoria necessaria para um novo registro*/
if(novo!=NULL)//se conseguiu alocar
{
novo->chave = chave;/*adiciona a chave digitada pelo usuario ao campo chave do novo vertice*/
novo->esquerdo = NULL;
novo->direito = NULL;
}
return novo;//retorna o endereco de memoria alocado ou NULL se nao conseguir alocar espaco
}
void inserir(struct Vertice** raiz, int chave)
{
int ok;
struct Vertice* novo;
struct Vertice* ptAux;
novo = alocaVertice(chave);
if (*raiz == NULL)/*se arvore esta vazia*/
{
*raiz = novo;
printf("RAIZ INICIAL adicionada com sucesso! \n");
system("pause");
}
else
{
ptAux = *raiz;
ok = 0; /*falso*/
while(!ok)
{
if (novo->chave > ptAux->chave)
{
if (ptAux->direito == NULL)
{
ptAux->direito = novo;
ok = 1; /*verdadeiro*/
printf("Nodo adicionado com sucesso! \n");
system("pause");
}
else
ptAux = ptAux->direito;
}
else if (ptAux->esquerdo == NULL)
{
ptAux->esquerdo = novo;
ok = 1;
printf("Nodo adicionado com sucesso! \n");
system("pause");
}
else
ptAux = ptAux->esquerdo;
}
}
}
void imprimir(struct Vertice* vertice)
{
struct Vertice* ptAux;
ptAux = vertice;
if (ptAux != NULL)
{
printf("Meu endereco = %d ", (int)ptAux);
printf("Filho Esquerdo = %d ", (int)ptAux->esquerdo);
printf("Filho Direito = %d ", (int)ptAux->direito);
printf("Chave = %d ", ptAux->chave);
printf("\n");
imprimir(ptAux->esquerdo);//chamada recursiva
imprimir(ptAux->direito);//chamada recursiva
}
}
void imprimirPre(struct Vertice* vertice) /* EXECUTA ENCAMINHAMENTO PRE-FIXADO */
{
struct Vertice* ptAux;
ptAux = vertice;
if (ptAux != NULL)
{
printf("Meu endereco = %d ", (int)ptAux);
printf("Filho Esquerdo = %d ", (int)ptAux->esquerdo);
printf("Filho Direito = %d ", (int)ptAux->direito);
printf("Chave = %d ", ptAux->chave);
printf("\n");
imprimirPre(ptAux->esquerdo);//chamada recursiva
imprimirPre(ptAux->direito);//chamada recursiva
}
}
void imprimirPos(struct Vertice* vertice) /* EXECUTA ENCAMINHAMENTO POS-FIXADO */
{
struct Vertice* ptAux;
ptAux = vertice;
if (ptAux != NULL)
{
imprimirPos(ptAux->esquerdo);//chamada recursiva
imprimirPos(ptAux->direito);//chamada recursiva
printf("Meu endereco = %d ", (int)ptAux);
printf("Filho Esquerdo = %d ", (int)ptAux->esquerdo);
printf("Filho Direito = %d ", (int)ptAux->direito);
printf("Chave = %d ", ptAux->chave);
printf("\n");// INCOMPLETO
}
}
void imprimirCentral(struct Vertice* vertice) /* EXECUTA ENCAMINHAMENTO CENTRAL */
{
struct Vertice* ptAux;
ptAux = vertice;
if(ptAux!=NULL)
{
imprimirCentral(ptAux->esquerdo);//chamada recursiva
printf("Meu endereco = %d ", (int)ptAux);
printf("Filho Esquerdo = %d ", (int)ptAux->esquerdo);
printf("Filho Direito = %d ", (int)ptAux->direito);
printf("Chave = %d ", ptAux->chave);
printf("\n");
imprimirCentral(ptAux->direito);//chamada recursiva
}
}
void excluirFolha(struct Vertice** raiz, int chave)
{
struct Vertice* ptAux;
struct Vertice* ptAnt;
ptAux = *raiz;
if ((*raiz)-> chave == chave)
{
if (((*raiz)->esquerdo == NULL) && ((*raiz)->direito == NULL)) // se RAIZ nao houver filhos...
{
(*raiz) = NULL;
printf("CHAVE RAIZ EXCLUIDA COM SUCESSO!");
system("pause");
}
else
{
printf("Nodo nao e uma folha, erro ao excluir!");
system("pause");
}
}
else // se nao houver filhos...
{
while ((ptAux)->chave != chave && ptAux != NULL)
{
ptAnt = ptAux;
if (chave < (ptAux)->chave)
{
ptAux = ptAux->esquerdo;
}
else
{
ptAux = ptAux->direito;
}
}
if(ptAux == NULL)
printf("\nValor nao encontrado");
else
{
if (((ptAux)->esquerdo == NULL) && ((ptAux)->direito == NULL))
{
free(ptAux);
if(chave < ptAnt->chave)
ptAnt->esquerdo = NULL;
else if(chave > ptAnt->chave)
ptAnt->direito = NULL;
printf("CHAVE EXCLUIDA COM SUCESSO!");
system("pause");
}
else
{
printf("Nodo nao e uma folha, erro ao excluir!");
system("pause");
}
}
}
}
void procuraChave(struct Vertice* raiz, int chave)
{
struct Vertice* ptAux;
struct Vertice* ptAnt;
ptAux = raiz;
while ((ptAux)->chave != chave && ptAux != NULL)
{
ptAnt = ptAux;
if (chave < (ptAux)->chave)
{
ptAux = ptAux->esquerdo;
}
else
{
ptAux = ptAux->direito;
}
}
if(ptAux == NULL)
printf("\nValor nao encontrado");
else
{
if (ptAux != raiz)
{
printf("\nChave do nodo pai: %d\n", ptAnt->chave);
}
else
printf("\nNao e possivel mostrar a chave do nodo pai pois e a raiz\n");
imprimir(ptAux);
}
}
int verificaGrauEsq(struct Vertice* ptAux, int grauE) // INCOMPLETO FALTA SE ->ESQUERDO && ->DIREITO !=NULL ENTAO PESQUISAR
{
int grau;
do // verifica grau da esquerda
{
grau++;
if(ptAux->esquerdo == NULL)
ptAux=ptAux->direito;
else(ptAux->direito == NULL);
ptAux=ptAux->esquerdo;
}while(ptAux->esquerdo !=NULL || ptAux->direito !=NULL);
return grau;
}
int verificaGrauDir(struct Vertice* ptAux, int grauD) // INCOMPLETO
{
int grau;
do // verifica grau da esquerda
{
grau++;
if(ptAux->esquerdo == NULL)
ptAux=ptAux->direito;
else if(ptAux->direito == NULL)
ptAux=ptAux->esquerdo;
}while(ptAux->esquerdo !=NULL || ptAux->direito !=NULL);
return grau;
}
void verificaAVL(struct Vertice* vertice) // INCOMPLETO
{
struct Vertice* ptAux;
struct Vertice* ptRFixo;
int grauE=1; // variavel grau recebe 1, pq se entrar na função é pq a arvore não é vazia, logo tem pelo menos 1 grau
int grauD=1; // variavel grau recebe 1, pq se entrar na função é pq a arvore não é vazia, logo tem pelo menos 1 grau
ptAux = vertice; // atribui a raiz a uma variavel que sofrera alterações.
grauE = verificaGrauEsq(ptAux->esquerdo, grauE); // INCOMPLETO
grauD = verificaGrauDir(ptAux->direito, grauD); // INCOMPLETO
}
int main()
{
int op = 0, chave;
struct Vertice* ptRaiz = NULL;/*cria um ponteiro para armazenar o endereço da raiz da Arvore*/
while (op != 9)
{
op = menu();
switch (op)
{
case 1:/*inserir vertice*/
printf("Digite o valor do vertice: ");
scanf("%d",&chave);
inserir(&ptRaiz, chave);
break;
case 2:/*imprimir*/
printf("\n");
if(ptRaiz!=NULL)//se Arvore tem conteudo
imprimir(ptRaiz);
else
printf("\nArvore Vazia\n\n");
break;
case 3:/*excluir folha*/
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
printf("Digite a chave do nodo a ser excluido:");
scanf("%d",&chave);
excluirFolha(&ptRaiz,chave);
}
else
printf("\nArvore Vazia!\n\n");
break;
case 4:/*Procura chave*/
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
printf("Digite a chave do nodo a ser buscado:");
scanf("%d",&chave);
procuraChave(ptRaiz,chave);
}
else
printf("\nArvore Vazia!\n\n");
break;
case 5: /*Caminhamento pre-fixado*/
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
imprimirPre(ptRaiz);
}
else
printf("\nArvore Vazia!\n\n");
break;
case 6: /*Caminhamento pos-fixado*/
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
imprimirPos(ptRaiz);
}
else
printf("\nArvore Vazia!\n\n");
break;
case 7: /*Caminhamento central*/
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
imprimirCentral(ptRaiz);
}
else
printf("\nArvore Vazia!\n\n");
break;
case 8: /* Verifica se a arvore e AVL */
if(ptRaiz!=NULL)//se Arvore tem conteudo
{
verificaAVL(ptRaiz);
}
else
printf("\nArvore Vazia!\n\n");
break;
default:
printf("\nOpcao Invalida!\n\n");
break;
}
}
return 0;
}