Baixe o app para aproveitar ainda mais
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 ); }
Compartilhar