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.
