Solução proposta para tarefa de 22.11

#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));
 }
}

codigo da aula de 08.11.2016

/******************************************************************************/
/*              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");
}

avl...

x

Árvores AVL

links para materiais diversos sobre árvores AVL
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm https://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture7.pdf
http://visualgo.net/bst
https://en.wikipedia.org/wiki/AVL_tree
https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap7b.pdf
http://www.geeksforgeeks.org/avl-tree-set-1-insertion/

cõdigo feito na aula de 25.10.2016

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

#define SIZE 1000
#define No int

typedef struct Tr {
  No *raiz;    // ponteiro para a raiz  
} Arvore;

Arvore *criaArvore (){
  Arvore *r;
  int i;
  r=(Arvore *) malloc (sizeof(Arvore));
  r->raiz= (No *) calloc (SIZE, sizeof(No));
  printf ("%p, %p\n", r, r->raiz);
   // para facilitar pois pretendo implementar a árvore em um array, se o valor armazenado for zero, então o espaço estará vazio.

 /* for (i=0;i<20;i++) {
     r->raiz[i]=i+10;
  }*/

  return r;
}

// caso não haja, retorna NULL
No *esquerda (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice*=2;
  indice++;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

No *direita (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice*=2;
  indice+=2;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

No *pai (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice--;
  indice/=2;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

void imprimeNo (No *n) {
  printf ("%04d ", *n);
}

void imprimeArvorePorNo (Arvore *A, No *n, int altura) {
    int i;
    if ((n)&&(*n!=0)) {
      imprimeArvorePorNo (A, direita(A, n), altura+1);
      for (i=0;i<altura;i++) {
       printf ("      ");
      }
      imprimeNo (n);
      puts ("");
      imprimeArvorePorNo (A, esquerda(A, n), altura+1);
    }
}

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

void removeArvore (Arvore *A) {
  free (A->raiz);
  free (A);
}

void Insere(Arvore *A, int valor, No *p) {
  if(*p == 0 ){//verifica se a posicao esta vazia
    *p = valor;
}   
 else if(valor > *p){// 
    p= direita (A, p) ;
    Insere(A, valor,  p);
  } 
    else{
    p=esquerda (A, p);
    Insere(A, valor,  p);
        
    } 


}

No *busca(Arvore *A, No *raiz, int chave ) {
    No *atual = raiz;
    if(*atual == 0){
        printf("erro");
        return NULL ;
        }
        
    if(*atual == chave){
        printf("%d" , *atual);
        return atual;
        
    }
    
    else if (chave >*atual){
         atual = direita(A, atual);
             
    }
    if (chave <*atual){
         atual = esquerda(A, atual);
         
    }

    busca(A, atual, chave);
}   
    remover(Arvore *A, No *raiz, int chave){
        busca(A, A->raiz,chave);
    }
void main (void) {
   Arvore *A;
   A=criaArvore();
   printf ("%p, %p\n", A, A->raiz);
   
   Insere(A, 100, A->raiz);
   Insere(A, 50, A->raiz );
   Insere(A, 200, A->raiz );
   Insere(A, 300, A->raiz );
   Insere(A, 40, A->raiz );
   Insere(A, 150, A->raiz );
   Insere(A, 500, A->raiz );
   Insere(A, 50, A->raiz );
   Insere(A, 600, A->raiz );
   Insere(A, 42, A->raiz );
   Insere(A, -442, A->raiz );
   busca(A, A->raiz,2000);
   
   imprimeArvore(A);
   removeArvore(A);
}

Imagem da execução do exemplo da árvore binária

O objetivo do código é prover as funções de impressão e acesso aos elementos da árvore de forma que sejam independentes de implementação.
A implementação usada é estática e posicional (usa um array e a relação entre os elementos é definida por sua posição no array).
É necessário testar se árvores "com buracos" são impressas corretamente.
A tarefa será implementar as funções de inserção, busca e remoção de nó.
É permitido trocar a estrutura de dados, caso você ache mais fácil de entender se usar outra.
Antes do fim da aula chamar para que sua solução seja avaliada.

Importante: o preenchimento foi feito para testar as funções de impressão. Rigorosamente, o posicionamento dos elementos na árvore fazem com que ela NÃO seja uma árvore binária de busca pois essa, por definição, tem os elementos menores que a raiz na subárvore da esquerda e os elementos maiores na subárvore da direita. (por outro lado, a árvore é um heap mínimo ;)

Arvore binária de busca código fonte do exemplo

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

#define SIZE 1000
#define No int

typedef struct Tr {
  No *raiz;    // ponteiro para a raiz  
} Arvore;

Arvore *criaArvore (){
  Arvore *r;
  int i;
  r=(Arvore *) malloc (sizeof(Arvore));
  r->raiz= (No *) calloc (SIZE, sizeof(No));
  printf ("%p, %p\n", r, r->raiz);
   // para facilitar pois pretendo implementar a árvore em um array, se o valor armazenado for zero, então o espaço estará vazio.

  for (i=0;i<20;i++) {
     r->raiz[i]=i+10;
  }

  return r;
}

// caso não haja, retorna NULL
No *esquerda (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice*=2;
  indice++;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

No *direita (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice*=2;
  indice+=2;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

No *pai (Arvore *A, No *n) {
  // como a árvore é implementada em um array e a funcao usa ponteiros, faz aritmetica de ponteiros para conseguir os índices.
  int indice=n-A->raiz;
  indice--;
  indice/=2;
  return (indice >= SIZE)?NULL:A->raiz+indice;
}

void imprimeNo (No *n) {
  printf ("%d ", *n);
}

void imprimeArvorePorNo (Arvore *A, No *n, int altura) {
    int i;
    if ((n)&&(*n!=0)) {
      imprimeArvorePorNo (A, direita(A, n), altura+1);
      for (i=0;i<altura;i++) {
       printf ("  ");
      }
      imprimeNo (n);
      puts ("");
      imprimeArvorePorNo (A, esquerda(A, n), altura+1);
    }
}

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

void removeArvore (Arvore *A) {
  free (A->raiz);
  free (A);
}
void main (void) {
   Arvore *A;
   A=criaArvore();
   printf ("%p, %p\n", A, A->raiz);
   imprimeArvore(A);
   removeArvore(A);
}

formatado em bedaux.net

resultado da execução de matriz.c

fabio@fabio-System-Product-Name:~/Desktop/array$ gcc matriz.c fabio@fabio-System-Product-Name:~/Desktop/array$ ./a.out 1000 1012 1024 1036 1048 1060 1072 1084 1096 1108 1120 1132 1001 1013 1025 1037 1049 1061 1073 1085 1097 1109 1121 1133 1002 1014 1026 1038 1050 1062 1074 1086 1098 1110 1122 1134 1003 1015 1027 1039 1051 1063 1075 1087 1099 1111 1123 1135 1004 1016 1028 1040 1052 1064 1076 1088 1100 1112 1124 1136 1005 1017 1029 1041 1053 1065 1077 1089 1101 1113 1125 1137 1006 1018 1030 1042 1054 1066 1078 1090 1102 1114 1126 1138 1007 1019 1031 1043 1055 1067 1079 1091 1103 1115 1127 1139 1008 1020 1032 1044 1056 1068 1080 1092 1104 1116 1128 1140 1009 1021 1033 1045 1057 1069 1081 1093 1105 1117 1129 1141 0x7fff890a3870 0x7fff890a38a0 0x7fff890a38d0 0x7fff890a3900 0x7fff890a3930 0x7fff890a3960 0x7fff890a3990 0x7fff890a39c0 0x7fff890a39f0 0x7fff890a3a20 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 fabio@fabio-System-Product-Name:~/Desktop/array$

Matrizes estruturadas (da apostila de W. Honda e I. Paraboni

   O objetivo deste post é esclarecer idéias que fazem matrizes esparsas (no caso estruturadas) tão importantes.
   A álgebra de matrizes (ou álgebra linear...) é aplicada para modelar ou para simular os mais variados processos dentre eles: processos químicos (sistemas de reações químicas que resultam em um ou mais produtos de grande valor), mecânica de fluidos (consequentemente previsão do tempo - com impacto na agricultura), circuitos elétricos (desde distribuição de energia até projeto e simulação de circuitos integrados), processamento de imagens (imagens médicas, realidade virtual, jogos,...).
    Nestes processos milhares ou até milhões de sistemas lineares com milhares de variáveis precisam ser resolvidos. É algo que um computador faz, mas precisa de muita memória e capacidade de processamento, OU de algoritmos que aproveitam a estrutura do problema (das matrizes) para economizar memória e processamento.
    Em problemas muito grandes é até comum que as matrizes que os representam tenham muitos elementos nulos (da ordem de 90% da matriz) que poderiam não ser representados e com isso não ocupar memória.
    Deve-se considerar também a ordem e frequência com que os elementos da matriz serão visitados. Por exemplo em um produto de matrizes: A x B, A os elementos de A serão varridos por linhas e os de B por colunas, em ordem. Ligar os elementos não nulos nas linhas e nas colunas (listas ligadas) pode ser uma boa estratégia para poupar memória e operações. Algo similar ocorre na fatoração LU (triangularização de matrizes) e na fatoração QR - estas duas usadas para resolver sistemas lineares.
    Na fatoração LU, as matriz M é fatorada em duas: L - triangular inferior e U - triangular superior. Em geral as duas são armazenadas juntas (é o que faz o algoritmo de Gauss), mas apenas U é necessária para resolver o sistema. Neste caso seria vantajoso armazenar apenas U. Existe uma forma de armazenar e indexar matrizes triangulares.
   Da mesma forma, existem formas de armazenar matrizes diagonais e matrizes tridiagonais.


Matriz diagonal
(a) tamanho do vetor de alocação: n
(b) elementos não nulos m(i,j) são tais que i == j;
(c) endereçamento: m(i,j) == V(i) ou j...

Em código:

double *criaMatrizDiagonal (int n) {
// cria uma matriz diagonal n x n
    return malloc (n*sizeof (double));   // usa só n elementos
}

double leMatrizDiagonal (double *M, int i, int j) {
    if (i==j) return M[i];
    return 0.0;
}

Matriz tridiagonal
(a) tamanho do vetor de alocação: 3n – 2
(b) elementos não nulos m(i,j) são tais que |i –j| <= 1
(c) endereçamento ordenada por linhas,m[i, j ] == v[(2*i+ j –2)]

Em código:

double *criaMatrizTridiagonal (int n) {
// cria uma matriz tridiagonal n x n
    return malloc ((3*n-2)*sizeof (double));   // usa só 3n-2 elementos
}

double leMatrizTridiagonal (double *M, int i, int j) {
    if (abs(i-j)<=1) return M[(2*i+j-2)];
    return 0.0;
}


Matriz triangular inferior
a) tamanho do vetor de alocação (supondo matriz quadrada)- Há n^2 elementos na matriz;-Há n elementos na diagonal principal; - Logo, há (n^2+ n) / 2 elementos não nulos.
(b) elementos não nulos: Na triangular superior, m[i,j] == 0 se i < j. Na triangular inferior, m[i,j] == 0 se i>j.
(c) endereçamento:
    Triangular superior ordenada por colunas, m[i, j ] == v[(i^2-i) / 2+ j]
    Triangular inferior ordenada por linhas, m[i, j ] == v[(j^2-j) / 2+ i ]

Em código:

double *criaMatrizTriangularSuperior (int n) {
// cria uma matriz Triangular Superior n x n
    return malloc ((n*(n+1)/2)*sizeof (double));   // usa só (n^2+n)/2 elementos
}

double leMatrizTriangularInferior (double *M, int i, int j) {
    if (i>=j) return M[(i*i-i)/2+j)];
    return 0.0;
}

Nota: usando interfaces e vinculação tardia a chamada dos métodos pode ser unificada e a implementação da estrutura de dados pode ser ocultada, criando uma interface única independente da estrutura subjacente.

Matriz em C - entendendo a estrutura

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

void main (void) {
   int m[10][12];
   int i, j;
   /*Usa uma funcao para mapear uma matriz 10x12 no array de 120 elementos.*/
   for (i=0;i<10;i++) {
      for (j=0;j<12;j++) {
         m[i][j]=i+j*12+1000;
      }
   }
   for (i=0;i<10;i++) {
      for (j=0;j<12;j++) {
         printf ("%d ", m[i][j]);
      }
   }
   /*Tentando hackear a estrutura:*/
   for (i=0;i<10;i++) {
      printf ("%p ", m[i]);  /* eh ponteiro?*/
   }
   /*Sim! mas veja os valores: eles saltam de 48 em 48 bytes - 
     a região de memória eh continua! */
   /* o conteudo eh ponteiro ou eh inteiro? */
#if 0
   for (i=0;i<10;i++) {
      printf ("%p ", *(m[i]));  /* o conteúdo eh ponteiro?*/
   }
/*
fabio@fabio-virtual-machine:~/Documents/array$ gcc matriz.c 
matriz.c: In function ‘main’:
matriz.c:26:15: warning: format ‘%p’ expects argument of type ‘void *’, but argument 2 has type ‘int’ [-Wformat=]
       printf ("%p ", *(m[i]));  
               ^
o erro indica que o conteúdo é inteiro!!!!
*/
#endif
   for (i=0;i<10;i++) {
      printf ("%d ", *(m[i]));  /* eh inteiro entao...*/
   }

}