# Alberi - parte 2
## Somma Nodi Contenuta in un Altro Albero
Dati due alberi binari, scrivere una funzione che restituisce 1 se la somma di tutti i nodi foglia di uno è uguale al valore di uno dei nodi dell’altro, o viceversa.

// Funzione per calcolare la somma dei nodi foglia di un albero
int sommaFoglie(Tree root) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Caso foglia: aggiungo il valore alla somma
    if (root->left == NULL && root->right == NULL) return root->data;

    // Sommo ricorsivamente le foglie dei sottoalberi
    return sommaFoglie(root->left) + sommaFoglie(root->right);
}

// Funzione per verificare se un valore è presente come nodo in un albero
int trovaNodo(Tree root, int value) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Se trovo il valore, restituisco 1
    if (root->data == value) return 1;

    // Cerco ricorsivamente nei sottoalberi
    return trovaNodo(root->left, value) || trovaNodo(root->right, value);
}

// Funzione principale per verificare la condizione
int verificaSommaUgualeNodo(Tree root1, Tree root2) {
    // Calcolo la somma dei nodi foglia del primo albero
    int somma_foglie1 = sommaFoglie(root1);

    // Controllo se la somma dei nodi foglia del primo albero
    // corrisponde a uno dei nodi del secondo albero
    if (trovaNodo(root2, somma_foglie1)) {
        return 1;
    }

    // Calcolo la somma dei nodi foglia del secondo albero
    int somma_foglie2 = sommaFoglie(root2);

    // Controllo se la somma dei nodi foglia del secondo albero
    // corrisponde a uno dei nodi del primo albero
    if (trovaNodo(root1, somma_foglie2)) {
        return 1;
    }

    return 0;
}

---

## Numero di Elementi Uguali
Si scriva una funzione che, dato un albero e un intero k, restituisce 1 se l’albero ha esattamente k elementi uguali tra loro.
Si implementino due versioni, una senza utilizzare strutture ausiliarie e un'altra che utlizzi delle strutture ausiliarie.

### Soluzione SENZA Strutture Ausiliarie

// Funzioni
int contaOccorrenze(Tree root, int value) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Conta il nodo corrente se il valore coincide
    int count = 0;
    if(root->data == value) count = 1;

    // Somma le occorrenze nei sottoalberi
    return count + contaOccorrenze(root->left, value) + contaOccorrenze(root->right, value);
}

int verificaKElementi(Tree current_root, int k, Tree original_root) {
    // Caso base: albero vuoto
    if (current_root == NULL) return 0;

    // Conta quante volte il valore del nodo corrente appare nell'albero
    int occorrenze = contaOccorrenze(original_root, current_root->data);

    // Se il valore appare esattamente k volte, restituisco 1
    if (occorrenze == k) return 1;

    // Altrimenti, continuo a verificare nei sottoalberi
    // Nota: ignoro i nodi già verificati
    int res_sx = verificaKElementi(current_root->left, k, original_root);
    int res_dx = verificaKElementi(current_root->right, k, original_root);

    return res_sx || res_dx;
}

==:warning: La soluzione presentata a lezione, come fatto notare da due vostri colleghi, non analizzava un caso chiave, ovvero quando i nodi sono frammentati in due sottoalberi diversi. La soluzione presentata riportata qui, invece, risolve il problema contando le occorrenze a partire sempre dalla radice originale. Per fare ciò, bisogna passare tra una chiamata e l'altra la radice originale.==

### Soluzione con Struttura di Appoggio
Uso una lista compressa ausiliaria:

// Nodo per la lista di conteggio
typedef struct CountNode {
    int value;
    int count;
    struct CountNode *next;
} CountNode;
typedef CountNode *pCountNode;

Con le seguenti funzioni di gestione:

pCountNode aggiornaLista(pCountNode head, int value) {
    pCountNode curr = head;

    // Cerca il valore nella lista
    while (curr != NULL) {
        if (curr->value == value) {
            curr->count++;
            return head; // Aggiornato
        }
        curr = curr->next;
    }

    // Valore non trovato, aggiungi nuovo nodo
    pCountNode new_node = (pCountNode)malloc(sizeof(CountNode));
    if (new_node == NULL) {
        printf("Errore di allocazione.\n");
        return head;
    }
    new_node->value = value;
    new_node->count = 1;
    new_node->next = head;

    return new_node;
}

void liberaLista(pCountNode head) {
    pCountNode curr;
    while (head != NULL) {
        curr = head;
        head = head->next;
        free(curr);
    }
}

int verificaKOccorrenze(pCountNode head, int k) {
    pCountNode curr = head;
    while (curr != NULL) {
        if (curr->count == k) {
            return 1; // Trovato
        }
        curr = curr->next;
    }
    return 0; // Non trovato
}

La soluzione salva i nodi dell’albero all’interno della lista compressa che viene popolata con la ricorsione, la lista quindi avrà in ogni nodo un valore associato a quante volte appare nell'albero.

pCountNode popolaLista(Tree root, pCountNode head) {
    // Albero vuoto
    if (root == NULL) return head;

    // Aggiorna con il nodo corrente
    head = aggiornaLista(head, root->data);

    // Scorro i sottoalberi
    head = popolaLista(root->left, head);
    head = popolaLista(root->right, head);

    return head;
}

int verificaKElementi(Tree root, int k){
	// Popolo la lista
	pCountNode head = NULL;
	head = popolaLista(root, head);
	
	// Verifico che ci siano k elementi uguali
	int res = verificaKOccorrenze(head, k);
	
	// Svuoto la lista
	liberaLista(head);
	
	return res;
}

---

## Albero Isobato

Si scriva una funzione che prende in input un albero e restituisce 1 se l’albero è isobato, 0 altrimenti.

Un albero si dice isobato se tutti i cammini dalla radice alle foglie hanno la stessa lunghezza.

### Soluzione 1

// Funzione per calcolare il cammino di lunghezza massima
int maxDepth(Tree root){
    if(root == NULL) return 0;

    int depth_sx, depth_dx;
    depth_sx = maxDepth(root->left);
    depth_dx = maxDepth(root->right);
    
    if(depth_sx > depth_dx) return depth_sx + 1;
    else return depth_dx + 1;
}
// Funzione per calcolare il cammino di lunghezza minima
int minDepth(Tree root){
    if(root == NULL) return 0;

    int depth_sx, depth_dx;
    depth_sx = minDepth(root->left);
    depth_dx = minDepth(root->right);

    if(depth_sx == 0) return depth_dx + 1;
    if(depth_dx == 0) return depth_sx + 1;
    
    if(depth_sx < depth_dx) return depth_sx + 1;
    else return depth_dx + 1;
}

int alberoIsobato(Tree root){
    return maxDepth(root) == minDepth(root);
}

==**Nota:** le righe 20 e 21 servono a gestire correttamente il caso in cui un nodo ha un solo figlio, altrimenti si restituisce al chiamante la `min_depth` sbagliata. Ad esempio, nel caso cerchiato nella figura sottostante, si restituisce correttamente al chiamante 2, altrimenti si restituirebbe 1.==


### Soluzione 2

// Funzione ausiliaria per calcolare la profondità e verificare l'isobatia
int verificaProfondita(Tree root, int *isIsobato) {
    // Caso base: albero vuoto
    if (root == NULL) return 0;

    // Calcolo ricorsivo della profondità dei sottoalberi
    int profondita_sx = verificaProfondita(root->left, isIsobato);
    int profondita_dx = verificaProfondita(root->right, isIsobato);

    // Verifica se i sottoalberi hanno la stessa profondità
    if (profondita_sx != profondita_dx) {
        *isIsobato = 0; // Non è isobato
    }

    // Restituisce la profondità attuale del sottoalbero
		int profondita_corrente;
		if (profondita_sx > profondita_dx) {
		    profondita_corrente = profondita_sx;
		} else {
		    profondita_corrente = profondita_dx;
		}
		return profondita_corrente + 1;
}
    
int alberoIsobato(Tree root) {
    // Variabile per tracciare se l'albero è isobato
    int isIsobato = 1;
    verificaProfondita(root, &isIsobato);
    return isIsobato;
}

---

## Alberi Ternari Isobati

Scrivere una funzione che dice se un albero ternario è isobato oppure no.

Si consideri la seguente definizione:

typedef struct NodeTree {
    int data;
    struct NodeTree * left;
    struct NodeTree * right;
    struct NodeTree * center;
} NodeTree; 
typedef NodeTree * Tree;

// Funzione ausiliaria
int verificaIsobato(Tree root, int profondita_corrente, int *profondita_foglia) {
    // Caso base: nodo vuoto
    if (root == NULL) {
        return 1; // Nodo vuoto non influisce sull'isobatia
    }

    // Caso base: foglia
    if (root->left == NULL && root->right == NULL && root->center == NULL) {
        // Se è la prima foglia incontrata, salvo la profondità
        if (*profondita_foglia == -1) {
            *profondita_foglia = profondita_corrente;
            return 1; // Fin qui l'albero è isobato
        }
        // Controllo che la profondità della foglia corrente sia uguale alla profondità salvata
        return *profondita_foglia == profondita_corrente;
    }

    // Caso ricorsivo
    int is_left_isobato = verificaIsobato(root->left, profondita_corrente + 1, profondita_foglia);
    int is_right_isobato = verificaIsobato(root->right, profondita_corrente + 1, profondita_foglia);
    int is_center_isobato = verificaIsobato(root->center, profondita_corrente + 1, profondita_foglia);

    return is_left_isobato && is_right_isobato && is_center_isobato;
}

// Funzione principale
int alberoIsobato(Tree root) {
    int profondita_foglia = -1; // Per salvare la profondità della prima foglia incontrata
    return verificaIsobato(root, 0, &profondita_foglia);
}

---
## Alberi Artussiani

Si scriva una funzione che prende in input un albero e restituisce 1 se tale albero è artussiano.

Un albero si dice artussiano se e solo se è composto da:

- nodi foglia
- nodi con un solo figlio
- nodi con due figli aventi lo stesso numero di discendenti



### Soluzione 1

int contaNodi(Tree root){
	if(root == NULL) return 0;
	return contaNodi(root->left) + contaNodi(root->right) + 1;
}

int alberoArtussiano(Tree root){
	// Caso base: albero vuoto
	if(root == NULL) return 1;

	// Caso base: foglia
	if(root->left == NULL && root->right == NULL) return 1;
	
	// Analizzo il branch di destra
	if(root->left == NULL) return alberoArtussiano(root->right);
	
	// Oppure analizzo il branch di sinistra
	if(root->right == NULL) return alberoArtussiano(root->left);
	
	// Se ho entrambi i branch disponibili, devo verificare che:
	// Entrambi i branch hanno gli stessi nodi
	// Entrambi i sottoalberi sono artussiani
	if(contaNodi(root->left) == contaNodi(root->right) && alberoArtussiano(root->left) && alberoArtussiano(root->right)) return 1;
	
	return 0;
}

### Soluzione 2

// Funzione helper per calcolare numero di nodi e verificare se l'albero è artussiano
int alberoArtussianoHelper(Tree root, int *nodi) {
    // Caso base: albero vuoto
    if (root == NULL) {
        *nodi = 0;
        return 1;
    }

    // Variabili per il conteggio dei nodi dei sottoalberi
    int nodi_sx = 0, nodi_dx = 0;

    // Verifica se i sottoalberi sono artussiani
    int sx_artussiano = alberoArtussianoHelper(root->left, &nodi_sx);
    int dx_artussiano = alberoArtussianoHelper(root->right, &nodi_dx);

    // Calcola il numero di nodi totali
    *nodi = nodi_sx + nodi_dx + 1;

    // Verifica la condizione artussiana
    return sx_artussiano && dx_artussiano && (nodi_sx == nodi_dx);
}

// Funzione principale
int alberoArtussiano(Tree root) {
    int nodi = 0;
    return alberoArtussianoHelper(root, &nodi);
}

# Ordinamento

Si scrivano le funzioni iterative per implementare selection sort e bubble sort per ordinare un array di interi.

Si scriva la funzione ricorsiva merge sort per ordinare un array di interi

// Librerie
#include <stdio.h>

#define N 10

// Prototipi
void stampaArray(int[], int);
void selectionSort(int[], int);
void bubbleSort(int[], int);
void mergeSort(int[], int, int);
void merge(int[], int, int, int);
void copiaArray(int[], int[], int);

// Main
int main(){
    int v[N] = {2,4,1,6,5,9,5,10,4,2};
    int t[N];

    printf("Array: ");
    stampaArray(v, N);

    printf("Selection Sort: ");
    copiaArray(v, t, N);
    selectionSort(t, N);
    stampaArray(t, N);

    printf("Bubble Sort: ");
    copiaArray(v, t, N);
    bubbleSort(t, N);
    stampaArray(t, N);

    printf("Merge Sort: ");
    copiaArray(v, t, N);
    mergeSort(t, 0, N-1);
    stampaArray(t, N);

    return 0;
}

// Funzioni
void selectionSort(int v[], int dim){
    for(int i = 0; i < dim; i++){
        for(int j = i + 1; j < dim; j++){
            if(v[i] > v[j]){
                int tmp = v[j];
                v[j] = v[i];
                v[i] = tmp;
            }
        }
    }
}

void bubbleSort(int v[], int dim){
    int i, j, n_swap,tmp;
    for(i = 0; i < dim - 1; i++){
        n_swap = 0;
        for(j = 0; j < dim - i - 1; j++){
            if(v[j] > v[j+1]){
                tmp = v[j];
                v[j] = v[j+1];
                v[j+1] = tmp;
                n_swap++;
            }
        }
        if(n_swap == 0) break;
    }
}

void mergeSort(int v[], int start, int end){
    int mid;
    if(start < end){
        mid = (start + end)/2;
        mergeSort(v, start, mid);
        mergeSort(v, mid + 1, end);
        merge(v, start, end, mid);
    }
}

void merge(int v[], int start, int end, int mid){
    int i=start, j=mid+1, k=start, copy[N];
    // faccio il merge fino alla fine di una delle due porzioni
    while((i <= mid) && (j <= end)){
        if(v[i] > v[j]){
            copy[k] = v[j];
            j++;
        }
        else{
            copy[k] = v[i];
            i++;
        }
        k++;
    }
    // finisco la copia della prima porzione (se necessario)
    while(i <= mid){
        copy[k] = v[i];
        k++;
        i++;
    }
    // OPPURE finisco la copia della seconda porzione (se necessario)
    while(j <= end){
        copy[k] = v[j];
        k++;
        j++;
    }
    // copio "copy" nell'array di partenza, ma solo nella porzione interessata
    for(i=start; i <= end; i++){
        v[i] = copy[i];
    }
}

void stampaArray(int v[], int dim){
    printf("[");
    for(int i = 0; i<dim; i++) printf("%d,", v[i]);
    printf("]\n");
}

void copiaArray(int src[], int dest[], int dim){
    for(int i = 0; i < dim; i++){
        dest[i] = src[i];
    }
}