Alberi n-ari

Supponiamo di rappresentare alberi n-ari non vuoti etichettati con interi per mezzo di espressioni in base alla seguente regola

  • se la radice dell'albero T ha etichetta l e n sotto-alberi T1,... Tn, la sua rappresentazione è
    l n t1 ... tn
    dove t1 ... tn sono le espressioni che rappresentano gli alberi T1,... Tn.

Esempio L'espressione

1 2 2 1 3 2 1 0 2 0 -2 3 4 0 0 2 -6 0 0 0 3 1 -1 2 1 0 4 1 -6 0

rappresenta l'albero

AlberoNario.jpg

  1. Scrivere una funzione che legge da input la sequenza che rappresenta un albero n-ario e costruisce la rappresentazione dell'albero n-ario sotto forma di albero binario (il figlio sinistro punta al primo figlio nella lista dei figli del nodo, mentre il figlio destro punta al fratello successivo nella lista dei figli del padre del nodo).
  2. Scrivere una funzione che preso un albero n-ario rappresentato per mezzo di un albero binario stampa la sequenza che lo rappresenta.
  3. Scrivere una funzione che preso un albero n-ario rappresentato mediante albero binario inverte l'ordine della lista dei figli di ogni nodo. Ovvero, indicando con t* la trasformazione di un albero t, se t = l n t1 ... tn, allora t* = l n tn* ... t1*.
    Esempio L'albero dell'esempio precedente diviene
    AlberoNarioRev.jpg

-- StefanoGuerrini - 05 Jun 2007


This topic: Programmazione2pz > WebHome > AnnoAcc0607 > HomeWork0607 > HomeWork060704
Topic revision: r1 - 2007-06-05 - StefanoGuerrini
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback