#define _CRT_SECURE_NO_WARNINGS

#include "stdio.h"
#include "stdlib.h"

struct Node {
    struct Node *left;
    double data;
    struct Node *right;
};

void InOrderPrdouble(struct Node* root) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%f  ", root->data);
        return;
    }
    if (root->left != NULL) {
        InOrderPrdouble(root->left);
    }
    printf("%f  ", root->data);
    if (root->right != NULL) {
        InOrderPrdouble(root->right);
    }
}

struct Node *GetNewNode(double data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* Insert(struct Node *root, double data) {
    if (root == NULL) {
        root = GetNewNode(data);
        return root;
    }
    else if (data <= root->data) {
        root->left = Insert(root->left, data);
    }
    else {
        root->right = Insert(root->right, data);
    }
    return root;
}

void funzione(struct Node *root,double altezza_attuale,double *count_foglie, double *altezze_tot) {
    if ((root->left == NULL) && (root->right == NULL)) {  //raggiunto foglia
        (*count_foglie)++;
        (*altezze_tot) += altezza_attuale;
        return;
    }

    if (root->left != NULL) {
        funzione(root->left, altezza_attuale + 1, count_foglie, altezze_tot);
    }

    if (root->right != NULL) {
        funzione(root->right, altezza_attuale + 1, count_foglie, altezze_tot);
    }

}


int main() {

    struct  Node *root = NULL;
    root = Insert(root, 15);
    root = Insert(root, 10);
    root = Insert(root, 20);
    root = Insert(root, 25);
    root = Insert(root, 8);
    root = Insert(root, 12);
    root = Insert(root, 35);
    root = Insert(root, 45);
    printf("albero = ");
    InOrderPrdouble(root);

    double count_foglie = 0;
    double altezze_tot = 0;
    double altezza_attuale = 0;

    funzione(root, altezza_attuale, &count_foglie, &altezze_tot);

    printf("\n\n%f  ", count_foglie);
    printf("%f", altezze_tot);

    printf("\ncammino medio = %f", altezze_tot/count_foglie);
}