Arvore AVL

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<locale.h>
struct arvore 
{ 
 struct arvore *esquerda;
 int no;
 struct arvore *direita;
};
typedef struct arvore arvore_no;
typedef arvore_no *arvore_no_ponteiro;
struct fila_t 
{
 arvore_no_ponteiro no;
 struct fila_t *proximo;
};
typedef struct fila_t fila;
void inserir_no(arvore_no_ponteiro *ponteiro_arvore, int valor);
void ordem(arvore_no_ponteiro ponteiro_arvore);
void pre_ordem(arvore_no_ponteiro ponteiro_arvore);
void pos_ordem(arvore_no_ponteiro ponteiro_arvore);
void nova_ordem(arvore_no_ponteiro root);
int deletar_no(arvore_no_ponteiro *ponteiro_arvore, int valor);
void saida_da_arvore(arvore_no_ponteiro raiz, int espaco_total);
void enfileirar(fila **cabeca, fila **traz, arvore_no_ponteiro valor);
arvore_no_ponteiro desenfileirar(fila **cabeca, fila **traz);
arvore_no_ponteiro buscar_na_arvore( arvore_no_ponteiro ponteiro_arvore, int valor);
int main(void)
{ 
 setlocale(LC_ALL, "Portuguese");
 int i, item; 
 arvore_no_ponteiro raiz_ponteiro = NULL;
 srand(time(NULL)); 
 printf("\n Valores contidos na árvore: ");
 for (i=1;i<=10;i++) 
 { 
 item=1+rand()%10;
 printf("%3d", item);
 inserir_no(&raiz_ponteiro, item);
 }
 printf("\n");
 printf("\n Insira o valor para ser removido: ");
 scanf("%d", &item);
 if(deletar_no(&raiz_ponteiro, item)) 
 {
 printf("\n Número inexistente: %d", item);
 return -1;
 }
 printf("\n Percurso em pré-ordem: ");
 pre_ordem(raiz_ponteiro);
 printf("\n");
 printf("\n Percurso em ordem: ");
 ordem(raiz_ponteiro);
 printf("\n");
 printf("\n Percurso em pós-ordem: 	 ");
 pos_ordem(raiz_ponteiro);
 printf("\n");
 printf("\n Números ordenados novamente:	 ");
 nova_ordem(raiz_ponteiro);
 printf("\n");
 puts("\n Exibição da árvore:");
 printf("\n");
 saida_da_arvore(raiz_ponteiro, 0);
 putchar('\n');
 system("pause>>NULL");
 return 0;
}
void inserir_no(arvore_no_ponteiro *ponteiro_arvore, int valor)
{
	if(*ponteiro_arvore==NULL)
	{
		*ponteiro_arvore=(arvore_no*)malloc(sizeof(arvore_no));
		if(*ponteiro_arvore!=NULL)
		{
			(*ponteiro_arvore)->no=valor;
			(*ponteiro_arvore)->esquerda=NULL;
			(*ponteiro_arvore)->direita=NULL;
		}
		else
		{
			printf("\n %d Não inserido, sem memória disponível.");
 	}
	}
	else 
	{
		if(valor<(*ponteiro_arvore)->no)
		{
			inserir_no(&((*ponteiro_arvore)->esquerda), valor);
	 }
		else 
		{
			if (valor>(*ponteiro_arvore)->no)
			{
				inserir_no(&((*ponteiro_arvore)->direita), valor);
	 	}
			else
			{ 
				printf("->dup");
			}
		}
	}
}
void ordem(arvore_no_ponteiro ponteiro_arvore)
{ 
 if(ponteiro_arvore!=NULL) 
 { 
 ordem(ponteiro_arvore->esquerda);
 printf(" %3d ", ponteiro_arvore->no);
 ordem(ponteiro_arvore->direita);
 }
}
void pre_ordem(arvore_no_ponteiro ponteiro_arvore)
{ 
 if(ponteiro_arvore!=NULL) 
 { 
 printf(" %3d ", ponteiro_arvore->no);
 pre_ordem(ponteiro_arvore->esquerda);
 pre_ordem(ponteiro_arvore->direita);
 }
}
void pos_ordem(arvore_no_ponteiro ponteiro_arvore)
{ 
 if(ponteiro_arvore!=NULL) 
 { 
 pos_ordem(ponteiro_arvore->esquerda);
 pos_ordem(ponteiro_arvore->direita);
 printf(" %3d ", ponteiro_arvore->no);
 }
}
int deletar_no(arvore_no_ponteiro *ponteiro_arvore, int valor)
{
 arvore_no_ponteiro pai=buscar_na_arvore( *ponteiro_arvore, valor);
 arvore_no_ponteiro *filho;
 arvore_no_ponteiro atual;
 if((pai==NULL)||(*ponteiro_arvore==NULL))
 {
 	 return 1;
 }
 if(pai->esquerda!=NULL && pai->esquerda->no==valor)
 filho=&pai->esquerda;
 else
 filho=&pai->direita;
 if((*filho )->esquerda==NULL && (*filho)->direita==NULL) 
 {
 *filho=NULL;
 free(*filho);
 }
 else if(((*filho)->esquerda!=NULL) ^ ((*filho)->direita!=NULL)) 
 {
 pai= *filho;
 if((*filho)->esquerda!=NULL)
 *filho=(*filho)->esquerda;
 else
 *filho=(*filho)->direita;
 free(pai);
 }
 else 
 {
 atual=(*filho)->esquerda;
 while(atual->direita!=NULL) 
	 {
	 atual=atual->direita;
 }
 pai= *filho; 
 atual->direita=(*filho)->direita;
 (*filho)->direita= NULL;
 *filho=(*filho)->esquerda;
 free(pai);
 }
 return 0;
}
arvore_no_ponteiro buscar_na_arvore(arvore_no_ponteiro ponteiro_arvore, int valor)
{ 
	arvore_no_ponteiro retp=ponteiro_arvore;
 	if(retp!=NULL) 
 	{
 	if((retp->esquerda!= NULL && retp->esquerda->no==valor) || (retp->direita!= NULL && retp->direita->no==valor))
	 	{ 
	 	return retp;
 	}
 	if(retp->no>valor)
 	{
	 	return buscar_na_arvore(retp->esquerda, valor);
 	}
	 	else
	 	{
	 		return buscar_na_arvore(retp->esquerda, valor);
 	}
 }
 return NULL;
}
void enfileirar(fila **cabeca, fila **traz, arvore_no_ponteiro valor)
{
 fila*nova_arvore;
 if((nova_arvore=(fila*)malloc(sizeof(fila)))==NULL) 
 {
 printf("\n Não é possível alocar a memória.");
 return;
 }
 nova_arvore->no=valor;
 nova_arvore->proximo=NULL;
 if(*cabeca==NULL) 
 {
 *cabeca=nova_arvore;
 }
 else 
 {
 (*traz)->proximo=nova_arvore;
 }
 *traz=nova_arvore;
} 
arvore_no_ponteiro desenfileirar(fila **cabeca, fila **traz)
{
 arvore_no_ponteiro valor;
 fila *temporario=*cabeca;
 valor=(*cabeca)->no;
 *cabeca=(*cabeca)->proximo;
 if(*cabeca==NULL) 
 {
 *traz=NULL;
 }
 free(temporario);
 return valor;
} 
void nova_ordem(arvore_no_ponteiro raiz)
{
 fila *cabeca=NULL, *traz=NULL;
 arvore_no_ponteiro no_atual;
 enfileirar(&cabeca, &traz, raiz);
 while(cabeca!=NULL && (no_atual=desenfileirar(&cabeca, &traz))!=NULL) 
 {
 printf(" %3d ", no_atual->no); 
 if(no_atual->esquerda!= NULL)
 {
	 		enfileirar(&cabeca, &traz, no_atual->esquerda);
 }
	 if(no_atual->direita!= NULL)
	 {
	 		enfileirar(&cabeca, &traz, no_atual->direita);
	 }
 }
} 
void saida_da_arvore(arvore_no_ponteiro raiz, int espaco_total)
{
 int i;
 arvore_no_ponteiro no_atual=raiz;
 while(no_atual!=NULL) 
 {
 saida_da_arvore(no_atual->direita, espaco_total+5);
 for(i=1;i<=espaco_total;i++)
 {
	 putchar(' ');
 }
	 printf("%d\n", no_atual->no);
 no_atual=no_atual->esquerda;
 espaco_total+=5;
 }
}