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