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