Fábio Nakano, Ph.D: novembro 2016

C++ code colored by C++2HTML

#include <stdio.h>
#include <stdlib.h>
#include "abb.h"

No *novoNo (int valor) {
// retorna null caso nao consiga alocar
 No *n;
 n= (No *) calloc (1, sizeof(No));
 if (n) n->valor=valor;
 return n;
}

Arvore * criaArvore() {
 Arvore * r;
 r = (Arvore * ) malloc(sizeof(Arvore));
 return r;
}

void imprimeNo(No * n) {
 printf("{%d, %d, %d} ", n->valor, n->altura, n->f);
}

void imprimeArvorePorNo(No * n, int nivel) {
 int i;
 if (n) {
  imprimeArvorePorNo(n->dir, nivel+1);
  for (i = 0; i < nivel; i++) {
   printf("           ");
  }
  imprimeNo(n);
  puts("");
  imprimeArvorePorNo(n->esq, nivel+1);
 }
}

void imprimeArvore(Arvore * A) {
 if ((A == NULL) || (A -> raiz == NULL)) {
  printf("arvore inexistente ou vazia.\n");
 } else {
  imprimeArvorePorNo(A->raiz, 0);
 }
}

void removeArvore(Arvore *A) { /* incompleto */
 free(A->raiz);
 free(A);
}
/*
No *buscaPorNo(Arvore *A, No *n, int valor) {
 int i;
 if ((n) && ( *n != 0)) { // ainda há onde buscar
    //printf ("%d ", *n);
  if ( *n == valor) return n; // achou
  else if ( *n < valor) return buscaPorNo(A, direita(A, n), valor);
  return buscaPorNo(A, esquerda(A, n), valor);
 }
 return NULL;
}


No *buscaNaArvore(Arvore *A, int valor) {
 if ((A == NULL) || (A->raiz == NULL)) {
  printf("arvore inexistente ou vazia.\n");
 } else {
  return buscaPorNo(&A->raiz, valor);
 }
}
*/

void calculaAlturaEF (No *n) {
 // dado que a altura dos filhos de n está correta, calcula a altura de n.
 int hd=-1;
 if (n->dir) hd=(n->dir)->altura;
 int he=-1;
 if (n->esq) he=(n->esq)->altura;

 n->altura=1+((hd>he)?hd:he);
 n->f=hd-he;
}


void inserePorNo(No **n, int valor) {
// como em insereNaArvore o caso da arvore vazia é tratado
// nao preciso me ocupar com ele aqui, mas preciso me ocupar se a posicao da folha nao
// existir
 if (*n==NULL) {
  *n= novoNo (valor);  // eh uma folha - altura zero e f==0 - foi criado com os valores certos.
  return;
 }
 if ((*n)->valor<valor) {
  inserePorNo(&((*n)->dir), valor);
 } else {
  inserePorNo(&((*n)->esq), valor);
 }

 // acerta campos altura e balanceamento do nó
 /*
 int hd=-1;
 if ((*n)->dir) hd=((*n)->dir)->altura;
 int he=-1;
 if ((*n)->esq) he=((*n)->esq)->altura;

 (*n)->altura=1+((hd>he)?hd:he);
 (*n)->f=hd-he;
 */
 calculaAlturaEF (*n);
}

void insereNaArvore(Arvore * A, int valor) {
 if (A == NULL) {
  printf("arvore inexistente.\n");
 } else {
  inserePorNo(&(A->raiz), valor);
 }
}

void rotacaoD (No **eixo) {
 No *e, *d;
 e=(*eixo)->esq;
 d=(*eixo)->dir;
 (*eixo)->esq=e->dir;
 e->dir=*eixo;
 calculaAlturaEF(*eixo);
 *eixo=e;
 calculaAlturaEF(*eixo);
}

void rotacaoE (No **eixo) {
 No *e, *d;
 e=(*eixo)->esq;
 d=(*eixo)->dir;
 if (!d) {
  puts ("Não há subarvore direita: não é possível rotacionar à esquerda.");
  return;
 }
 (*eixo)->dir=d->esq;
 d->esq=*eixo;
 calculaAlturaEF(*eixo);
 *eixo=d;
 calculaAlturaEF(*eixo);
}

void tentaBalancearPorNo(No **n) {
 if (*n==NULL) {
  // o pai tem um ou zero filhos. e este ramo é vazio.
  return;
 }
 tentaBalancearPorNo(&((*n)->dir));
 tentaBalancearPorNo(&((*n)->esq));

/*
 // acerta campos altura e balanceamento deste nó
 int hd=-1;
 if ((*n)->dir) hd=((*n)->dir)->altura;
 int he=-1;
 if ((*n)->esq) he=((*n)->esq)->altura;

 (*n)->altura=1+((hd>he)?hd:he);
 (*n)->f=hd-he;
 */
 calculaAlturaEF(*n);  // talvez seja desnecessario pois não houve nenhuma rotação na descida
 if ((*n)->f >1) {// subarvore da direita eh mais alta
  if (((*n)->dir) && ((*n)->dir->f<-1)) {// subarvore da esquerda do filho da direita eh mais alta
   puts ("rotação a direita em torno do filho da direita");
   rotacaoD(&((*n)->dir));
  }
  puts ("rotação a esquerda em torno do no");
  rotacaoE(n);
 }
 if ((*n)->f <-1) {// subarvore da esquerda eh mais alta
  if (((*n)->esq) && ((*n)->esq->f>1)) {// subarvore da direita do filho da esquerda eh mais alta
   puts ("rotação a esquerda em torno do filho da esquerda");
   rotacaoE(&((*n)->esq));
  }
  puts ("rotação a direita em torno do no");
  rotacaoD(n);
 }
}

void tentaBalancear(Arvore *A) {
 if (A == NULL) {
  printf("arvore inexistente.\n");
 } else {
  tentaBalancearPorNo(&(A->raiz));
 }
}

C++ code colored by C++2HTML

/******************************************************************************/
/*              Este programa gerencia arvores AVL                            */
/*  Arvores AVL sao arvores balanceadas na altura.                            */
/*  O nome AVL vem de seus criadores Adelson Velsky e Landis, cuja primeira   */
/*    referência encontra-se no documento "Algoritmos para organização da     */
/*    informação" de 1962.                                                    */
/******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define true 1
#define false 0

//typedef int int;
typedef int TIPOCHAVE;
typedef struct aux {
 TIPOCHAVE chave;
 struct aux *esq;
 struct aux *dir;
 int bal; // fator de balanceamento (0, -1 ou +1) => altura direita - altura esquerda
} NO, *PONT;

/* cria um novo (aloca memoria e preenche valores) no com chave=ch e retorna 
       seu endereco */

PONT criarNovoNo(TIPOCHAVE ch){
 PONT novoNo = (PONT)malloc(sizeof(NO));
 novoNo->esq = NULL;
 novoNo->dir = NULL;
 novoNo->chave = ch;
 novoNo->bal = 0;
 return novoNo;
}

// Retorna o maior valor entre dois inteiros
int max(int a, int b){
 if (a>b) return a;
 return b;
}

// Retorna a altura de uma (sub-)arvore
int altura(PONT p){
 if (!p) return 0;
 else return 1 + max(altura(p->esq),altura(p->dir));
}

/* Exibe arvore Em Ordem         */
void exibirArvoreEmOrdem(PONT raiz){
 if (raiz == NULL) return;
 exibirArvoreEmOrdem(raiz->esq);
 printf("%d ",raiz->chave);
 exibirArvoreEmOrdem(raiz->dir);
}


/* Exibe arvore Pre Ordem         */
void exibirArvorePreOrdem(PONT raiz){
 if (raiz == NULL) return;
 printf("%d ",raiz->chave);
 exibirArvorePreOrdem(raiz->esq);
 exibirArvorePreOrdem(raiz->dir);
}

/* Exibe arvore Pos Ordem         */
void exibirArvorePosOrdem(PONT raiz){
 if (raiz == NULL) return;
 exibirArvorePreOrdem(raiz->esq);
 exibirArvorePreOrdem(raiz->dir);
 printf("%d ",raiz->chave);
}

/* Exibe arvore Em Ordem (com parenteses para os filhos)    */
void exibirArvore(PONT raiz){
 if (raiz == NULL) return;
 printf("%d[%d]",raiz->chave,raiz->bal);
 printf("(");     
 exibirArvore(raiz->esq);
 exibirArvore(raiz->dir);
 printf(")");     
}

/* Exibe arvore Pre-Ordem indicando pai de cada no    */
void exibirArvore2(PONT raiz, TIPOCHAVE chavePai){
 if (raiz == NULL) return;
 printf("(%d,%d) ",chavePai,raiz->chave);
 exibirArvore2(raiz->esq,raiz->chave);
 exibirArvore2(raiz->dir,raiz->chave);
}

// Verifica se árvore é AVL
int ehAVL(PONT p){
 int e,d;
 int ok = true;
 if(p){
  ok = ehAVL(p->esq);
  if(ok) ok = ehAVL(p->dir);
  if(ok){
   e = altura(p->esq);
   d = altura(p->dir);
   if(abs(e-d) <= 1) ok = true;  
   else ok = false;
  }
 }
 return(ok);
}

// Verifica se árvore é AVL
int ehAVL2(PONT p, int* alt){
    if (!p){
       *alt=0;
       return true;
    }
    int res;
    int d, e;
 res = ehAVL2(p->dir,&d);
 if (!res) return false;
 res = ehAVL2(p->esq,&e);
    if (!res) return false;
    if ((d-e<-1) || (d-e>1)) return false;
 *alt = max(d,e)+1; 
 return true; 
}

int atualizarBalanceamentoTotal(PONT raiz){
 if (!raiz) return 0;
 int d = atualizarBalanceamentoTotal(raiz->dir);
 int e = atualizarBalanceamentoTotal(raiz->esq);
 raiz->bal = d-e;
 return max(d,e)+1;
}

// Rotações à direita (LL e LR)
void rotacaoL(PONT *p){
 printf("Rotacao a esquerda, problema no no: %d\n",(*p)->chave);
 PONT u, v;
 u = (*p)->esq;
 if(u->bal == -1) {   // LL
  (*p)->esq = u->dir;
  u->dir = *p;
  (*p)->bal = 0;
  *p = u;
 } else {  // LR
  v = u->dir;
  u->dir = v->esq;
  v->esq = u;
  (*p)->esq = v->dir;
  v->dir = *p;
  if(v->bal == -1)(*p)->bal = 1;
  else (*p)->bal = 0;
  if(v->bal == 1) u->bal = -1;
  else u->bal = 0;
  *p = v;
 }
 (*p)->bal = 0; // balanço final da raiz (p) da subarvore
}

// Rotações à esquerda (RR e RL)
void rotacaoR(PONT *p){
 printf("Rotacao a direita, problema no no: %d\n",(*p)->chave);
 PONT u, v;
 u = (*p)->dir;
 if(u->bal == 1) {   // RR
  (*p)->dir = u->esq;
  u->esq = *p;
  (*p)->bal = 0;
  *p = u;
 } else {  // RL
  v = u->esq;
  u->esq = v->dir;
  v->dir = u;
  (*p)->dir = v->esq;
  v->esq = *p;
  if(v->bal == -1)(*p)->bal = 1;
  else (*p)->bal = 0;
  if(v->bal == 1) u->bal = -1;
  else u->bal = 0;
  *p = v;
 }
 (*p)->bal = 0; // balanço final da raiz (p) da subarvore
}

// Inserção AVL: p é inicializado com raiz e *alterou com false
// O retorno da função é o nó inserido, mas não precisa ser usado em main()

void inserirAVL(PONT *pp, TIPOCHAVE ch, int *alterou){
 PONT p = *pp;
 if(!p){
  *pp = criarNovoNo(ch);
  *alterou = true;
  //else printf("Criando no %d, filho de %d", ch, (*raiz)->chave);
 } else {
  if(ch < p->chave) {
            inserirAVL(&(p->esq), ch, alterou);
   if(*alterou)
    switch (p->bal) {
    case 1 : p->bal = 0;
    *alterou = false;
    break;
    case 0 : p->bal = -1;
    break;
    case -1: rotacaoL(pp);
    *alterou = false;
    break;
    }
  } else {
   inserirAVL(&(p->dir), ch, alterou);
   if(*alterou)
    switch (p->bal) {
    case -1: p->bal = 0;
    *alterou = false;
    break;
    case 0 : p->bal = 1;
    break;
    case 1 : rotacaoR(pp);
    *alterou = false;
    break;
    }
  }
 }
}

/* retorna o endereco do NO que contem chave=ch ou NULL caso a chave nao seja
       encontrada. Utiliza busca binaria recursiva                                */
PONT buscaBinaria(TIPOCHAVE ch, PONT raiz){
 if (raiz == NULL) return NULL;
 if (raiz->chave == ch) return raiz;
 if (raiz->chave<ch) 
  return buscaBinaria(ch,raiz->dir);
 return buscaBinaria(ch,raiz->esq);
}  

// Busca binária não recursiva devolvendo o nó pai
PONT buscaNo(PONT raiz, TIPOCHAVE ch, PONT *pai){
 PONT atual = raiz;
 *pai = NULL;
 while (atual) {
  if(atual->chave == ch)
   return(atual);
  *pai = atual;
  if(ch < atual->chave) atual = atual->esq;
  else atual = atual->dir;
 }
 return(NULL);
}

/* funcao auxiliar na destruicao (liberacao da memoria) de uma arvore */
void destruirAux(PONT subRaiz){
 if (subRaiz){
  destruirAux(subRaiz->esq);
  destruirAux(subRaiz->dir);
  free(subRaiz);
 }
}

/* libera toda memoria de uma arvore e coloca NULL no valor da raiz    */
void destruirArvore(PONT * raiz){
 destruirAux(*raiz);
 *raiz = NULL;
}

/* inicializa arvore: raiz=NULL */
void inicializar(PONT * raiz){
 *raiz = NULL;
}

void travessiaAux(PONT p, int *niv, TIPOCHAVE ch, int *achou) {
 if(p) {
  (*niv)++;// *niv = *niv + 1;
  if(p->chave == ch) *achou = true;
  else {
   travessiaAux(p->esq, niv, ch, achou);
   if(!(*achou)) travessiaAux(p->dir, niv, ch, achou);
   if(!(*achou)) *niv = *niv - 1;
  }
 }
}

/* Retorna true e o nivel de uma chave (caso seja encontrada) e false caso 
contrario.                                                                */
int travessia(PONT p, int *niv, TIPOCHAVE ch) {
 *niv = 0;
 PONT temp = buscaBinaria(ch,p);
 if (temp){
  int achou = false;
  travessiaAux(p, niv, ch, &achou);
  return true;
 }
 else return false;
}

void verificaEhAVL(PONT l){
     if (ehAVL(l)) printf("Arvore eh AVL.\n");
     else printf("PROBLEMA: a arvore nao eh mais AVL.\n");
}

void inserir(PONT *l, int x){
  TIPOCHAVE ch = x;
  //scanf("%d",&ch);
  int alterou;
  inserirAVL(l,ch,&alterou);
  printf("Elemento %d inserido corretamente.\n",ch);
}

void buscar(NO *l){
  TIPOCHAVE ch;
  scanf("%d",&ch);
  PONT posicao = buscaBinaria(ch,l);
  if (posicao != NULL) printf("Elemento %d encontrado no endereco %d.\n",ch,posicao);
  else printf("Nao foi possivel encontrar elemento %d.\n",ch);
}

void usaTravessia(NO *l){
  TIPOCHAVE ch;
  scanf("%d",&ch);
  int niv;
  if (travessia(l, &niv, ch)) printf("Elemento %d encontrado no nivel %d.\n",ch,niv);
  else printf("Nao foi possivel encontrar elemento %d.\n",ch);
}

void exibirEmOrdem(NO *l){
   printf("Em ordem: ");
   exibirArvoreEmOrdem(l); printf("\n");
}

void exibirArvoreP(NO *l){
   exibirArvore(l); printf("\n");
}

void exibirArvoreX(NO *l){
   printf("Arvore AVL: ");
   exibirArvore2(l,-1); printf("\n");
}

void exibirPreOrdem(NO *l){
   printf("Pre ordem: ");
   exibirArvorePreOrdem(l); printf("\n");
}

void exibirPosOrdem(NO *l){
   printf("Pos ordem: ");
   exibirArvorePosOrdem(l); printf("\n");
}

void help(){
  printf("Comandos validos: \n");
  printf("   i <chave1>: inserir elemento com chave=chave1\n");
  printf("   d : destruir (zerar) NO\n");
  printf("   h : exibir esta mensagem de ajuda\n");
  printf("   b <chave1>: exibir endereco do elemento com chave=chave1\n");
  printf("   0 : exibir arvore EM ordem.\n");
  printf("   1 : exibir arvore PRE-ordem.\n");
  printf("   2 : exibir arvore POS-ordem.\n");
  printf("   3 : exibir arvore parenteses.\n");
  printf("   9: verifica se arvore eh AVL.\n");
}

void destruir(PONT *l){
     destruirArvore(l);
     printf("Arvore zerada (toda memoria liberada).\n");
}

void removerf (PONT* pp, int ch/*, int *alterou*/){
    PONT l=*pp;
   // inserirAVL(&(p->esq), ch, alterou);
if(ch  < l->chave){
    removerf(&(l->esq), ch);
}
if(ch  > l->chave){
    removerf(&(l->dir), ch);
}
    if(ch  ==l->chave){
   free(l);
}else {
   printf("nao encontrou");
}
}

void imprimeArvorePorNo (PONT n, int altura) {
    int i;
    if (n) {
     imprimeArvorePorNo (n->dir, altura+1);
      for (i=0;i<altura;i++) {
       printf ("      ");
      }
       printf ("%04d ", n->chave);
      puts ("");
    imprimeArvorePorNo (n -> esq, altura+1);
    }
}

void imprimeArvore (PONT raiz) {
  if  (raiz==NULL){
    printf ("arvore inexistente ou vazia.\n");
  } else {
    imprimeArvorePorNo( raiz, 0);
  }
}

/*
int main()`
  PONT raiz;
  inicializar(&raiz);
  help();
  char comando = ' ';
  scanf("%c",&comando);
  while (comando != 'q'){
    switch (comando) {
      case 'i' : inserir(&raiz); break;
      case 'd' : destruir(&raiz); break;
      case 'h' : help(); break;
      case 'b' : buscar(raiz); break;
      case '0' : exibirEmOrdem(raiz); break;
      case '1' : exibirPreOrdem(raiz); break;
      case '2' : exibirPosOrdem(raiz); break;
      case '3' : exibirArvoreP(raiz); break;
      case '5' : exibirArvoreX(raiz); break;
      case '9' : verificaEhAVL(raiz); break;
      default: {while (comando != '\n') scanf("%c",&comando);};
    } 
    scanf("%c",&comando);
  }
  return 0;
}
 */

 int main () {
     printf ("hello\n"); //void inserirAVL(PONT *pp, TIPOCHAVE ch, int *alterou)
     PONT raiz;
     inicializar(&raiz);
     inserir(&raiz, 679);
  inserir(&raiz, 279);
     inserir(&raiz, 879);
     inserir(&raiz, 600);
     inserir(&raiz, 9);
     inserir(&raiz, 79);
     inserir(&raiz, 3679);
     inserir(&raiz, 6279);
      //removerf(&raiz,9);
     exibirEmOrdem(raiz);
     removerf(&raiz,6279);
   imprimeArvore (raiz);
     exibirArvoreX(raiz);
     printf ("hello\n");
}

Fábio Nakano, Ph.D

domingo, 27 de novembro de 2016

Solução proposta para tarefa de 22.11

terça-feira, 8 de novembro de 2016

codigo da aula de 08.11.2016

segunda-feira, 7 de novembro de 2016

terça-feira, 1 de novembro de 2016

Árvores AVL