1 // Go's concurrency primitives make it easy to 2 // express concurrent concepts, such as 3 // this binary tree comparison. 4 // 5 // Trees may be of different shapes, 6 // but have the same contents. For example: 7 // 8 // 4 6 9 // 2 6 4 7 10 // 1 3 5 7 2 5 11 // 1 3 12 // 13 // This program compares a pair of trees by 14 // walking each in its own goroutine, 15 // sending their contents through a channel 16 // to a third goroutine that compares them. 17 18 package main 19 20 import ( 21 "fmt" 22 "math/rand" 23 ) 24 25 // A Tree is a binary tree with integer values. 26 type Tree struct { 27 Left *Tree 28 Value int 29 Right *Tree 30 } 31 32 // Walk traverses a tree depth-first, 33 // sending each Value on a channel. 34 func Walk(t *Tree, ch chan int) { 35 if t == nil { 36 return 37 } 38 Walk(t.Left, ch) 39 ch <- t.Value 40 Walk(t.Right, ch) 41 } 42 43 // Walker launches Walk in a new goroutine, 44 // and returns a read-only channel of values. 45 func Walker(t *Tree) <-chan int { 46 ch := make(chan int) 47 go func() { 48 Walk(t, ch) 49 close(ch) 50 }() 51 return ch 52 } 53 54 // Compare reads values from two Walkers 55 // that run simultaneously, and returns true 56 // if t1 and t2 have the same contents. 57 func Compare(t1, t2 *Tree) bool { 58 c1, c2 := Walker(t1), Walker(t2) 59 for { 60 v1, ok1 := <-c1 61 v2, ok2 := <-c2 62 if !ok1 || !ok2 { 63 return ok1 == ok2 64 } 65 if v1 != v2 { 66 break 67 } 68 } 69 return false 70 } 71 72 // New returns a new, random binary tree 73 // holding the values 1k, 2k, ..., nk. 74 func New(n, k int) *Tree { 75 var t *Tree 76 for _, v := range rand.Perm(n) { 77 t = insert(t, (1+v)*k) 78 } 79 return t 80 } 81 82 func insert(t *Tree, v int) *Tree { 83 if t == nil { 84 return &Tree{nil, v, nil} 85 } 86 if v < t.Value { 87 t.Left = insert(t.Left, v) 88 return t 89 } 90 t.Right = insert(t.Right, v) 91 return t 92 } 93 94 func main() { 95 t1 := New(100, 1) 96 fmt.Println(Compare(t1, New(100, 1)), "Same Contents") 97 fmt.Println(Compare(t1, New(99, 1)), "Differing Sizes") 98 fmt.Println(Compare(t1, New(100, 2)), "Differing Values") 99 fmt.Println(Compare(t1, New(101, 2)), "Dissimilar") 100 } 101
