29 Aprile 2010 [Alberi Binari]

Nello svolgimento degli esercizi usare la seguente definizione di nodo:

typedef struct Node{
  int key;
  struct Node *left,*right;
} Node;

Es. 1.
Implementare la funzione

Node* make(int v)

che crea un nuovo nodo la cui chiave ha valore v.

Es. 2.
Implementare la funzione 

int to_string(Node* root,char* out_buffer)

che data la radice dell'albero da stampare, scrive in out_buffer la stringa che lo rappresenta.
Ad esempio l'albero avente la radice etichettata con 0, ed un figlio sinistro etichettato con 1,
dovra' essere rappresentato come: "([0] (1),())". (Usare l'aritmetica dei puntatori per implementare
la concatenazione tra 2 stringhe s1,s2 in O(|s2|)). (Che succede se la rappresentazione dell'albero
e' piu' grande del buffer?)

Es. 3.
Un albero binario e' 1-bilanciato se e' vuoto, oppure se per ogni nodo dell'albero sia il sottoalbero sinistro
che quello destro sono 1-bilanciati e la differenza tra l'altezza del sottoalbero sinistro e 
di quello destro e' al piu' 1. Implementare un predicato 

int is_balanced(Node* root,int k)

che decide se un albero e' 1-bilanciato. (Implementazione lineare nel numero di nodi dell'albero).

Es. 4.
Estendere la funzione precedente in maniera da decidere se un albero e' k-bilanciato.

Es. 5.
Definire una funzione make_tree(...) che dato in input un array ordinato di interi, costruisca un albero
binario bilanciato.