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

// Estrutura para o nó da árvore binária
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Funções para inserção da árvore binária
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Node* insert(struct Node* node, int data) {
    if (node == NULL) return newNode(data);
    if (data < node->data)
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);
    return node;
}

// Função de ordenação: Selection Sort
void selectionSort(int arr[], int n, int* comparisons) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            (*comparisons)++;
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// Função para gerar um vetor de inteiros únicos aleatórios
void generateRandomArray(int arr[], int size) {
    int i, num, exists;
    for (i = 0; i < size; i++) {
        do {
            exists = 0;
            num = rand() % 1000 + 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] == num) {
                    exists = 1;
                    break;
                }
            }
        } while (exists);
        arr[i] = num;
    }
}

// Função para imprimir a árvore binária em ordem
void printInOrder(struct Node* node) {
    if (node != NULL) {
        printInOrder(node->left);    // Visita o filho à esquerda
        printf("%d ", node->data);   // Imprime o valor do nó
        printInOrder(node->right);   // Visita o filho à direita
    }
}

// Função para imprimir a árvore binária em pré-ordem
void printPreOrder(struct Node* node) {
    if (node != NULL) {
        printf("%d ", node->data);   // Imprime o valor do nó
        printPreOrder(node->left);    // Visita o filho à esquerda
        printPreOrder(node->right);   // Visita o filho à direita
    }
}

int main() {
    // Parte 1: Exibir nomes e matrículas
    printf("Alunos:\n");
    printf("Endryo Tavares - 202051054689\n");
    printf("Pedro Guilherme - 202308418858\n");
    printf("Pedro Vanderlei - 202402821865\n");

    // Parte 2: Geração e Ordenação de Vetor
    int arr[100];
    int comparisons = 0;
    generateRandomArray(arr, 100);

    // Calcula o tempo de execução
    clock_t start, end;
    start = clock();

    // Realizando Selection Sort
    printf("\nUtilizando Selection Sort para ordenação...\n");
    selectionSort(arr, 100, &comparisons);

    end = clock();
    double time_spent = (double)(end - start) / CLOCKS_PER_SEC;

    // Parte 3: Apresentar resultados
    printf("Vetor ordenado: ");
    for (int i = 0; i < 100; i++) {
        printf("%d ", arr[i]);
    }
    printf("\nComparações realizadas: %d\n", comparisons);
    printf("Tempo de execução: %f segundos\n", time_spent);

    // Parte 4: Construção da Árvore Binária
    struct Node* root = NULL;
    for (int i = 0; i < 100; i++) {
        root = insert(root, arr[i]);
    }

    // Parte 5: Impressão da árvore binária
    printf("\nÁrvore Binária em ordem: ");
    printInOrder(root);
    printf("\n");

    // Parte 6: Impressão da árvore binária em pré-ordem
    printf("Árvore Binária em pré-ordem: ");
    printPreOrder(root);
    printf("\n");

    // Finalização
    printf("\n\nAgradecemos a presença de todos!\n");

    return 0;
}