Alberelli in Go

Sommario

Svolgimento dell’esercizio di implementazione di un albero con funzioni ricorsive in linguaggio Go.
Attratto da questo post su questo stesso blog di dikiyvolk, ho provato a reimplementare le funzioni di base per la struttura dati nel nuovo linguaggio targato Google, anziché in Delphi, come la versione originale, anche perché Juhan aveva citato proprio il Go nei commenti…
La visita dell’albero produce la stampa ordinata dei valori memorizzati nell’albero.

L’albero in Go

Il codice che vi riporto tutto d’un fiato di seguito, è molto simile a quello che si sarebbe scritto in C od in C++. Per eseguirlo cliccate su questo link del Go Playground e attivate il pulsante Run, oppure installate Go e date il comando di compilazione e poi quello di esecuzione intendendo che il file sorgente sia stato chiamato otree.go(adattate per il caso di sistemi operativi non derivati da unix):

$ go build otree.go
$ ./otree

Bando alle ciance, ecco il codice:

package main

import "fmt"

func main() {
    // setup a new tree
    tree := NewTree(10, 6, 4, 4, 3, 8, 12)
    tree.Visit()
    // adding a new element
    tree.AddData(9)
    fmt.Println()
    tree.Visit()
    // test an empty tree
    tree2 := NewTree()
    fmt.Println()
    tree2.Visit()
}

type OTree struct {
    root *leaf
}

type leaf struct {
    data        int
    left, right *leaf
}

func NewTree(nargs ...int) *OTree {
    ot := new(OTree)
    ot.AddData(nargs...)
    return ot
}

func (ot *OTree) AddData(nargs ...int) {
    if ot.root == nil && len(nargs) > 0 {
        ot.root = new(leaf)
        ot.root.data = nargs[0]
        nargs = nargs[1:]
    }
    for _, val := range nargs {
        addinteger(ot.root, val)
    }
}

func (ot *OTree) Visit() {
    if ot.root == nil {
        fmt.Println("The tree is empty.")
    } else {
        visit(ot.root)
    }
}

// core functions
func addinteger(t *leaf, n int) {
    switch {
    case n > t.data:
        if t.right == nil {
            t.right = new(leaf)
            t.right.data = n
        } else {
            addinteger(t.right, n)
        }
    case n < t.data:
        if t.left == nil {
            t.left = new(leaf)
            t.left.data = n
        } else {
            addinteger(t.left, n)
        }
    default:
        // duplicated insertion denied
    }
}

func visit(t *leaf) {
    if t.left != nil {
        visit(t.left)
    }
    fmt.Println(t.data)
    if t.right != nil {
        visit(t.right)
    }
}

Un saluto.
Alla prossima.
R.

Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: