btree

/* Compile com -std=c99, rode com ./a.out tamanho_da_arvore */
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>

/* Retorna o indice do nodo na arvore, ou UINT_MAX se nao encontrado -- O(n) */
size_t
index(int *tree, size_t nmemb, int node)
{
  size_t i = 0;
  while (i < nmemb && tree[i] != node)
    ++i;
  return i < nmemb ? i : -1;
}

int
parent(int *tree, size_t nmemb, int node)
{
  size_t i = index(tree, nmemb, node);
  if (i >= nmemb || !i)
    return INT_MAX;
  return tree[(i - 1) / 2];
}

int
left(int *tree, size_t nmemb, int node)
{
  size_t i = index(tree, nmemb, node);
  size_t ans = 2*i + 1;
  if (i >= nmemb || ans >= nmemb)
    return INT_MAX;
  return tree[ans];
}

int
right(int *tree, size_t nmemb, int node)
{
  size_t i = index(tree, nmemb, node);
  size_t ans = 2*i + 2;
  if (i >= nmemb || ans >= nmemb)
    return INT_MAX;
  return tree[ans];
}

int
main(int argc, char **argv)
{
  if (argc < 2) {
    fprintf(stderr, "Forneca o tamanho da arvore.\n");
    return EXIT_FAILURE;
  }
  size_t nmemb = (size_t)strtol(argv[1], NULL, 10);
  if (nmemb < 2) {
    fprintf(stderr, "Tamanho de pelo menos dois.\n");
    return EXIT_FAILURE;
  }
  int *tree = malloc(nmemb * sizeof(int));
  for (size_t i = 0; i < nmemb; ++i)
    tree[i] = i + 1;
  int e = tree[0];
  printf("Pai de %d: %d Esquerda: %d Direita: %d\n", e, parent(tree, nmemb, e),
      left(tree, nmemb, e), right(tree, nmemb, e));
  e = left(tree, nmemb, e);
  printf("Pai de %d: %d Esquerda: %d Direita: %d\n", e, parent(tree, nmemb, e),
      left(tree, nmemb, e), right(tree, nmemb, e));
  exit(EXIT_SUCCESS);
}