IV esercizio (11/05/05): alberi n-ari

Per rappresentare in C alberi n-ari etichettati con valori interi positivi, ci sono due tecniche principali:

• mediante nodi con lista dei figli (ogni nodo, oltre all'etichetta contiene un puntatore ad una lista di alberi)

• mediante alberi binari (ogni nodo dell'albero binario contiene un puntatore al primo figlio e uno al successivo fratello)

Si devono scrivere due funzioni che eseguono la conversione tra le due rappresentazioni, ovvero, una funzione prende un albero n-ario rappresentato mediante nodi con lista dei figli e lo converte nell'albero binario corrsipondete, mentre l'altra prende un albero binario e lo converte nel corrispondente albero n-ario rappresentato mediante nodi con lista dei figli.

Per completare l'esercizio, si devono anche scrivere una funzione che acquisisce un albero (ad esempio un albero binario), una funzione che stampa le precednti rappresentaizoni di alberi n-ari in accordo con una delle grammatiche per alberi n-ari fornite sotto, un main che dopo aver letto un albero e averlo memorizzato in una delle due forme, esegue le conversioni stampando ogni volta il risultato ottenuto.

Grammatiche per alberi n-ari

Supponiamo di avere alberi n-ari etichettati con interi. Una possibile rappresentazione lineare non ambigua può essere ottnuta scrivendo l'albero nel seguente modo:

• stampa l'etichetta della radice e, racchiusa tra parentesi tonde, stampa la lista dei sottoalberi della radice

che corrisponde alla seguente grammatica

T ::= n (T1 ... Tk)

dove n è un numero positivo (l'etichetta della radice dell'albero) e k ≥ 0 è il numero di figli della radice (per k = 0 il nodo è una foglia e tra parentesi non c'è nulla).

Un'altra possibile rappresentazione può essere ottenuta nel seguente modo

• se il nodo è una foglia, stampa l'etichetta della foglia e niente altro;
• altrimenti, tra parentesi tonde, stampa l'etichetta della foglia seguita dalla stampa della lista dei sottoalberi)

che corrisponde alla seguente grammatica

T ::= n | (n T1 ... Tk)

dove n è un numero positivo (l'etichetta della radice dell'albero) e k > 0 è il numero di figli della radice (in questo caso, se ci strova dentro le parentesi, non si può avere k = 0, che corrsiponderebbe ad un nodo foglia).

-- StefanoGuerrini - 12 May 2005