Altura de Árvore Binaŕia - ABB-AVL

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

/* 
 * File: main.c
 * Author: root
 *
 * Created on October 24, 2013, 7:23 AM
* Aluno.....: Leonardo Paulino Silva Matrícula: UC07022711
* Data......: 23/10/2009
*
* Enunciado.: 
* 
* 
* Sintese
*
* Objetivo..: a partir de numeros inseridos na arvore binaria de busca e uma avl, mostrar
* altura,
* 
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct s_cel{
	int elem, altura;
	struct s_cel *esq,*dir,*pai;
}cel;
typedef cel * no;
int adir (no p);
int aesq (no p);
int altura (no p);
int altura(no esse);
int Max(int Lhs, int Rhs);
void visita (no p);
void monta_arv (no raiz);
no cria_arv ();
no monta_ABB (no raiz, int valor);
no insere(no esse, int valor);
no criano(int valor);
no rodaUmDireita ( no K1 );
no rodaUmEsquerda ( no K2 );
no rodaDuploEsquerda ( no K3 );
no rodaDuploDireita ( no K1 );
no dir (no p);
no esq (no p);
no pai (no p);
no irmao (no p);
int main()
{
	int numero;
	no arvore=NULL;
 printf(" | [-1] -> Sair |\n");
 printf("----------------------------------------------------\n");
	while(numero!=-1){
		printf("Digite um numero int ...: ");
		scanf("%d",&numero);
		if(numero!=-1)
			arvore=monta_ABB(arvore,numero);
			arvore=insere(arvore,numero);
	}
	printf("\n\nAltura ABB ...: %d",altura(arvore));
	printf("\n\nAltura AVL ...: %d",altura(arvore));
	getch();
	return 0;
}
no cria_arv (){
 no arvore;
 arvore = (no)malloc(sizeof (cel));
 arvore->esq = NULL;
 arvore->dir = NULL;
 return (arvore);
}
no monta_ABB(no raiz, int valor){
	if(raiz==NULL){
		raiz=cria_arv();
		raiz->elem=valor;
		return raiz;
	}
	if(raiz->elem == valor)
		return raiz;
	if(raiz->elem < valor)
		raiz->dir=monta_ABB(raiz->dir,valor);
	else
		raiz->esq=monta_ABB(raiz->esq,valor);
	return raiz;
}
no dir (no p){
	if(p)
 	return p->dir;
	return NULL;
}
no esq (no p){
	if(p)
 	return p->esq;
	return NULL;
}
int altura (no p){
	int x,y;
	if(p==NULL)
		return 0;
	x=altura(p->esq);
	y=altura(p->dir);
	if(x>y){
		p->altura = x+1;
		return p->altura;
	}
	else{
		p->altura = y+1;
		return p->altura;
	}
}
no pai (no p){
	if(p)
 	return p->pai;
	return NULL;
}
int adir (no p){
	if ((esq(pai(p)))==p)
		return 1;
	return 0;
}
int aesq (no p){
	if ((dir(pai(p)))==p)
		return 1;
	return 0;
}
no irmao (no p){
	if (aesq(p))
		return dir(pai(p));
	return esq(pai(p));
}
void visita (no p){
	printf("%d, ",p->elem);
}
no insere(no esse, int valor){
 if(esse==NULL)
 esse=criano(valor);
 else {
 if(valor<esse->elem){
 esse->esq=insere(esse->esq,valor);
 if(altura(esse->esq)altura(esse->dir)==2)
 if(valor<esse->esq->elem)
 esse = rodaUmEsquerda(esse);
 else
 esse = rodaDuploEsquerda(esse);
 }
 else
 if(valor > esse->elem) {
 esse->dir=insere(esse->dir,valor);
 if(altura(esse->dir)altura(esse->esq)==2)
 if(valor > esse->dir->elem)esse = rodaUmDireita(esse);
 else
 esse = rodaDuploDireita(esse);
}
}
esse->altura = Max(altura(esse->esq),altura(esse->dir))+1;
return esse;
}
no criano(int valor) {
 no novo = malloc(sizeof(cel));
 novo->elem=valor;
 novo->esq=raiz->dir=NULL;
 novo->altura=0;
return novo;
}
int altura(no esse) {
 if(esse)
 return esse->altura;
 return 1;
}
int Max( int Lhs, int Rhs ) {
return Lhs > Rhs ? Lhs : Rhs;
}
no rodaUmDireita ( no K1 ) {
 no K2;
 K2 = K1->dir;
 K1->dir = K2>esq;
 K2->esq = K1;
 K1->altura=Max(altura(K1->esq),altura(K1->dir))+1;
 K2->altura=Max(altura(K2->dir),altura(K1)) + 1;
return K2; /* nova raiz */
}
no rodaUmEsquerda ( no K2 ) {
 no K1;
 K1 = K2->esq;
 K2->esq = K1>dir;
 K1->dir = K2;
 K2->altura=Max(altura(K2->esq),altura(K2->dir))+1;
 K1->altura=Max(altura(K1->esq),altura(K2)) + 1;
return K1; /* nova raiz */
}
no rodaDuploEsquerda ( no K3 ) {
 K3->esq=rodaUmDireita(K3->esq);
return rodaUmEsquerda( K3 );
}
no rodaDuploDireita ( no K1 ) {
 K1->dir=rodaUmEsquerda(K1->dir);
return rodaUmDireita ( K1 );
}