Dubbi su alberi binari

[Philo15]

Salve forum..
nella speranza che sia la sezione giusta vi pongo il mio dubbio.. sto volgendo degli esercizi in cui mi si chiede di scrivere un algoritmo (in pseudocodice) che ha in ingresso un albero binario dove i nodi interni sono operandi (+,-,*,/) e le foglie sono numeri o costanti ed in output mi scriva l'espressione algebrica con tanto di parentesi tonde...
non so come passare dalla descrizione "a parole" se così si può dire alla parte puramente di pseudocodice anche perchè penso di aver capito come procedere.. chi sa darmi una mano!?
grazie per le eventuali risposte..

[vict85]

Prova, come tentativo intermedio a pensare allo pseudocodice per scrivere (+ a b) invece di (a+b) che è più facile (scrivendo ogni parentesi o anche omettendole tanto la scrittura è unica). Come passaggio successivo prova a pensare a mettere tutte le parentesi, anche quelle inutili cioè ((a+b)+c) invece di a+b+c. Come ultima prova a vedere quando devi eliminare le parentesi...

[Philo15]

innanzitutto grazie per la risposta..
a scrivere uno pseudocodice per scrivere (+ a b) sinceramente non avevo pensato.. mi sono concentrato sul fatto di fare una visita dell'albero partendo dalle foglie (risalendolo fino alla radice) quindi cercare scrivere ((a+b)+etc.. ) che mi sembrava più facile..
una cosa del tipo:

Algoritmo StampaExp()
      IN: albero binario A_exp
      OUT: espressione legata all'albero binario
    
      v <- A_exp.root() //assegno la radice di A_exp a v
      StampaExp2(v)


Algoritmo StampaExp2(v)
       if isInternal(v) then
                  w <- leftChild(v) //assegno v il suo figlio sinistro se è interno
                  StampaExp2(w)

       //se v non è interno allora è una foglia
       w <- sibiling(v) // assegno a w il fratello di v
       p <- parent(v) //assegno a p il padre di v
       exp <- "("+v.getElement+p.getElement+w.getElement+")"
        
      //E' qui che mi blocco

questo è quel poco che sono riuscito a scrivere in pseudo-codice.. non sono sicuro che vada bene anzi..

[apatriarca]

Anche il pezzo che hai scritto è sbagliato. Ma secondo me ti fai più problemi di quelli necessari. Supponi di avere un nodo interno. Questo rappresenterà l'espressione (L op R) dove L è l'espressione contenuta nel sottoalbero a sinistra e R è l'espressione contenuta nel sottoalbero a destra. op è ovviamente l'operazione contenuta nel nodo interno. L'espressione di una foglia è costante. Partendo da queste premesse è quindi ovvio che per costruire l'intera espressione è sufficiente valutare per ogni nodo gli alberi destri e sinistri e quindi "incollare" le espressioni in quel modo. Qualcosa quindi come il seguente:

printTree (B op left right) = "(" ++ printTree left ++ print op ++ printTree right ++ ")"
printTree (L value) = print value

Il codice è in Haskell (mancano le definizioni ma per il resto potrebbe essere compilato) ma spero sia abbastanza chiaro. Ogni riga dice in che modo applico la funzione ad un nodo interno (B op left right) oppure ad una foglia (L value). left e right sono dei nodi, op è una operazione e value è un numero. Ti lascio il compito di scrivere questo metodo nel tuo pseudo-codice.

[Ska1]

Una cosa tipo

type Nodo
   val: Valore
   tipo: Tipo
   figlio1, figlio2: Nodo
end

proc Stampa(n: Nodo)
begin
    if n.tipo == COSTANTE
    then
        print n.val
    else
        print "(" + print(n.figlio1)+ print(n.val) + print(n.figlio2) + ")"
    end
end

[vict85]

"Ska":Una cosa tipo

type Nodo
   val: Valore
   tipo: Tipo
   figlio1, figlio2: Nodo
end

proc Stampa(n: Nodo)
begin
    if n.tipo == COSTANTE
    then
        print n.val
    else
        print "(" + print(n.figlio1)+ print(n.val) + print(n.figlio2) + ")"
    end
end

No, non è corretta: la soluzione è ricorsiva sui bracci. Comunque è quasi corretta.

[Ska1]

"vict85":[quote="Ska"]Una cosa tipo

type Nodo
   val: Valore
   tipo: Tipo
   figlio1, figlio2: Nodo
end

proc Stampa(n: Nodo)
begin
    if n.tipo == COSTANTE
    then
        print n.val
    else
        print "(" + print(n.figlio1)+ print(n.val) + print(n.figlio2) + ")"
    end
end

[/quote]

Sì che sbadato, nn ho messo le chiamate ricorsive

print "(" + Stampa(n.figlio1)+ print(n.val) + Stampa(n.figlio2) + ")"

Maledetto copia-incolla

[Philo15]

quante risposte.. grazie
ora mi è più chiaro come dovrei approcciarmi.. effettivamente mi ero complicato un pò la vita.. oggi cercherò di "trasportare" nel mio metodo le idee che mi avete gentilmente segnalato.. grazie ancora