Esercizio 4 (25/07/2017) esercitazione

es4.c

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

typedef struct node {
  int k;
  struct node *l, *r;
} node_t;

void insert(node_t **n, int k) {
  if(*n == NULL) {
    *n = (node_t*)malloc(sizeof(node_t));
    (*n)->k = k;
  } else {
    node_t *node = *n;
    if(node->k < k) {
      insert(&(node->r), k);
    } else {
      insert(&(node->l), k);
    }
  }
}

void delete(node_t *node) {
  if(node != NULL) {
    delete(node->l);
    delete(node->r);
    free(node);
  }
}

int rank(node_t *node, int base, int n) {
  if(node == NULL) return base;
  int r = rank(node->l, base, n);
  if(r == n / 2) printf("%d\n", node->k);
  return rank(node->r, r + 1, n);
}

int main(void) {
  int n, i, a;
  node_t *tree = NULL;
  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf("%d", &a);
    insert(&tree, a);
  }
  rank(tree, 0, n);
  delete(tree);
  return 0;
}