// Go's concurrency primitives make it easy to // express concurrent concepts, such as // this binary tree comparison. // // Trees may be of different shapes, // but have the same contents. For example: // // 4 6 // 2 6 4 7 // 1 3 5 7 2 5 // 1 3 // // This program compares a pair of trees by // walking each in its own goroutine, // sending their contents through a channel // to a third goroutine that compares them. package main import ( "fmt" "math/rand" ) // A Tree is a binary tree with integer values. type Tree struct { Left *Tree Value int Right *Tree } // Walk traverses a tree depth-first, // sending each Value on a channel. func Walk(t *Tree, ch chan int) { if t == nil { return } Walk(t.Left, ch) ch <- t.Value Walk(t.Right, ch) } // Walker launches Walk in a new goroutine, // and returns a read-only channel of values. func Walker(t *Tree) <-chan int { ch := make(chan int) go func() { Walk(t, ch) close(ch) }() return ch } // Compare reads values from two Walkers // that run simultaneously, and returns true // if t1 and t2 have the same contents. func Compare(t1, t2 *Tree) bool { c1, c2 := Walker(t1), Walker(t2) for { v1, ok1 := <-c1 v2, ok2 := <-c2 if !ok1 || !ok2 { return ok1 == ok2 } if v1 != v2 { break } } return false } // New returns a new, random binary tree // holding the values 1k, 2k, ..., nk. func New(n, k int) *Tree { var t *Tree for _, v := range rand.Perm(n) { t = insert(t, (1+v)*k) } return t } func insert(t *Tree, v int) *Tree { if t == nil { return &Tree{nil, v, nil} } if v < t.Value { t.Left = insert(t.Left, v) return t } t.Right = insert(t.Right, v) return t } func main() { t1 := New(100, 1) fmt.Println(Compare(t1, New(100, 1)), "Same Contents") fmt.Println(Compare(t1, New(99, 1)), "Differing Sizes") fmt.Println(Compare(t1, New(100, 2)), "Differing Values") fmt.Println(Compare(t1, New(101, 2)), "Dissimilar") }