!lezione-12.md

Esercizio della Lezione 12

esercizio-1.c

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

typedef struct albero {
  int value;
  struct albero *left;
  struct albero *right;
} Albero;

Albero *create_albero(int value) {
  Albero *albero = malloc(sizeof(Albero));
  
  albero->value = value;
  albero->left  = NULL;
  albero->right = NULL;
  
  return albero;
}

void albero_insert_rec(Albero *albero, int value) {
  if (albero->value > value) {
    if (albero->left == NULL) {
      albero->left = create_albero(value);
    }
    else {
      albero_insert_rec(albero->left, value);
    }
  }
  else {
    if (albero->right == NULL) {
      albero->right = create_albero(value);
    }
    else {
      albero_insert_rec(albero->right, value);
    }
  }
}

void albero_insert(Albero **albero, int value) {
  if (*albero == NULL) {
    *albero = create_albero(value);
  }
  else {
    albero_insert_rec(*albero, value);
  }
}

int albero_find(Albero *albero, int value, int depth) {
  if (albero != NULL) {
    if (albero->value == value) {
      return depth;
    }
    else {
      if (albero->value > value) {
        return albero_find(albero->left, value, depth + 1);
      }
      else {
        return albero_find(albero->right, value, depth + 1);
      }
    }
  }
  else {
    return -1;
  }
}

void print_albero(Albero *albero) {
  if (albero != NULL) {
    printf("%d < ", albero->value);
    print_albero(albero->left);
    printf(" | ");
    print_albero(albero->right);
    printf(" >");
  }
}

int main(void) {
  
  int count;
  Albero *albero = NULL;
  
  scanf("%d", &count);
  
  for (int i = 0; i < count; i++) {
    int n;
    scanf("%d", &n);
    
    albero_insert(&albero, n);
  }
  
  int n;
  
  while(1) {
    scanf("%d", &n);
    
    if (n < 0) 
      break;
    
    int depth = albero_find(albero, n, 0);
    
    if (depth == -1) {
      printf("NO\n");
    }
    else {
      printf("%d\n", depth);
    }
    
  };
  
  // print_albero(albero);
  
  return 0;
}

esercizio-2.c

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

#define MAX(A, B) ((A) > (B) ? (A) : (B))

typedef struct albero {
  int value;
  struct albero *left;
  struct albero *right;
} Albero;

Albero *create_albero(int value) {
  Albero *albero = malloc(sizeof(Albero));
  
  albero->value = value;
  albero->left  = NULL;
  albero->right = NULL;
  
  return albero;
}

void albero_insert_rec(Albero *albero, int value) {
  if (albero->value > value) {
    if (albero->left == NULL) {
      albero->left = create_albero(value);
    }
    else {
      albero_insert_rec(albero->left, value);
    }
  }
  else {
    if (albero->right == NULL) {
      albero->right = create_albero(value);
    }
    else {
      albero_insert_rec(albero->right, value);
    }
  }
}

void albero_insert(Albero **albero, int value) {
  if (*albero == NULL) {
    *albero = create_albero(value);
  }
  else {
    albero_insert_rec(*albero, value);
  }
}

int albero_height(Albero *albero) {
  if (albero == NULL) {
    return 0;
  }
  else {
    return MAX(albero_height(albero->left), albero_height(albero->right)) + 1;
  }
}

void print_albero(Albero *albero) {
  if (albero != NULL) {
    printf("%d < ", albero->value);
    print_albero(albero->left);
    printf(" | ");
    print_albero(albero->right);
    printf(" >");
  }
}

int main(void) {
  
  int count;
  Albero *albero = NULL;
  
  scanf("%d", &count);
  
  for (int i = 0; i < count; i++) {
    int n;
    scanf("%d", &n);
    
    albero_insert(&albero, n);
  }
  
  printf("%d\n", albero_height(albero));
  
  return 0;
}

esercizio-3.c

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

#define MAX(A, B) ((A) > (B) ? (A) : (B))

typedef struct albero {
  int value;
  struct albero *left;
  struct albero *right;
} Albero;

Albero *create_albero(int value) {
  Albero *albero = malloc(sizeof(Albero));
  
  albero->value = value;
  albero->left  = NULL;
  albero->right = NULL;
  
  return albero;
}

void albero_insert_rec(Albero *albero, int value) {
  if (albero->value > value) {
    if (albero->left == NULL) {
      albero->left = create_albero(value);
    }
    else {
      albero_insert_rec(albero->left, value);
    }
  }
  else {
    if (albero->right == NULL) {
      albero->right = create_albero(value);
    }
    else {
      albero_insert_rec(albero->right, value);
    }
  }
}

void albero_insert(Albero **albero, int value) {
  if (*albero == NULL) {
    *albero = create_albero(value);
  }
  else {
    albero_insert_rec(*albero, value);
  }
}

void print_albero(Albero *albero) {
  if (albero != NULL) {
    print_albero(albero->left);
    printf("%d\n", albero->value);
    print_albero(albero->right);
  }
}

int main(void) {
  
  int count;
  Albero *albero = NULL;
  
  scanf("%d", &count);
  
  for (int i = 0; i < count; i++) {
    int n;
    scanf("%d", &n);
    
    albero_insert(&albero, n);
  }
  
  print_albero(albero);
  
  return 0;
}