# :christmas_tree: Alberi
Albero Binario:

typedef struct TreeNode {
    int data;
    struct TreeNode * left;
    struct TreeNode * right;
} TreeNode;
typedef TreeNode * Tree;

---

# Numero di Foglie
Si scriva una funzione che, dato un albero binario, conti il numero delle foglie dell’albero.

int contaFoglie(Tree root){
	// Caso base: albero vuoto
	if(root == NULL) return 0;
	
	// Caso base: siamo arrivati a una foglia
	if(root->right == NULL && root->left == NULL) return 1;
	
	// Caso ricorsivo: non sono una foglia
	return contaFoglie(root->right) + contaFoglie(root->left);
}

---

# Numero di Branches (non foglie)
Si scriva una funzione che conta il numero di nodi che non sono foglie.

int contaNoFoglie(Tree root){
    // Se root è una foglia non conta niente
    if(root == NULL || (root->right == NULL && root->left == NULL)) return 0;
    
    // Se root non è una foglia conta 1
    return 1 + contaNoFoglie(root->left) + contaNoFoglie(root->right);
}

---

# Somma Nodi
Si scriva una funzione che restituisce la somma di tutti i nodi dell’albero.

// Sommare il valore dei nodi
int sommaNodi(Tree root){
    // Caso Base: albero vuoto
    if(root == NULL) return 0;

    // Caso Ricorsivo
    int value = root->data;
    int value_left = sommaNodi(root->left);
    int value_right = sommaNodi(root->right);

    return value + value_left + value_right;
}

---

# Inserimento Ordinato (per BST)
Si scriva una funzione che, dato un albero BST e un valore, inserisce un nuovo nodo nell'albero (senza ripetizioni).

Tree createNode(int value) {
    Tree newNode = (Tree)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Errore di allocazione memoria.\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Tree insert(Tree root, int value) {
    if (root == NULL) {
        return createNode(value); // Crea un nuovo nodo se il sottoalbero è vuoto
    }

    if (value < root->data) {
        root->left = insert(root->left, value); // Inserisce a sinistra
    } else if (value > root->data) {
        root->right = insert(root->right, value); // Inserisce a destra
    }
    // Se il valore è già presente, non fare nulla (niente duplicati)
    return root;
}

---

# Cerca Max
Si scriva una funzione che restituisce il massimo valore di un nodo contenuto in un albero.
Si implementino due funzioni, una che opera per alberi generici e una che opera per Alberi Binari di Ricerca (BST).

## Versione per Alberi Generici

int max2(int a, int b){
    if(a > b) return a;
    else return b;
}

int max3(int a, int b, int c){
    return max2(a, max2(b, c));
}

int cercaMax(Tree root){
    // Caso Albero Vuoto (ci entro solo se l'albero di partenza è vuoto)
    // Oppure se un nodo non foglia ha un solo figlio
    if(root == NULL) return 0;

    // Caso Foglia
    if(root->left == NULL && root->right == NULL) return root->data;

    // Caso Ricorsivo
    int value = root->data;
    int max_left = cercaMax(root->left, err);
    int max_right = cercaMax(root->right, err);

    return max3(value, max_left, max_right);
}

## Versione per BST

int cercaMaxOrdinato(Tree root){
	if(root == NULL) return 0;
	
	if(root->right == NULL) return root->data;
	
	return cercaMaxOrdinato(root->right, err);
}

==**Nota:** come si gestisce il caso in cui l'albero di partenza è vuoto?==

---

# Alberi Identici
Scrivere una funzione che prende in inout due alberi e restituisce 1 se i due sono identici

int alberiIdentici(Tree root1, Tree root2){
    // Casi base
    if(root1 == NULL && root2 == NULL) return 1;
    if(root1 == NULL || root2 == NULL) return 0;

    // Casi ricorsivi
    int condizione_nodo = root1->data == root2->data;
    int condizione_left = alberiIdentici(root1->left, root2->left);
    int condizione_right = alberiIdentici(root1->right, root2->right);

    return condizione_nodo && condizione_left && condizione_right;
}

---