Tags:
create new tag
view all tags

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

Topic revision: r1 - 2007-06-05 - StefanoGuerrini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback