Monday, December 14, 2015

Golang Exercise: Equivalent Binary Trees

code:

package main

import "golang.org/x/tour/tree"
import "fmt"


// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
 if t == nil {
  close(ch)
  return
 }
 if t.Left != nil {
  Walk(t.Left, ch)
 }
 ch <- t.Value
 //fmt.Println("send ", t.Value)
 if t.Right != nil {
  Walk(t.Right, ch)
 }
}


// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) (b_same bool) {
 c1 := make(chan int)
 c2 := make(chan int)
 b_same = true
 go Walk(t1, c1)
 go Walk(t2, c2)
 for i := 0; i < 10; i++ {
  //fmt.Println("get ", <-c1, <-c2)
  if <-c1 != <-c2 {
   b_same = false
   break
  }
 }
 return
}


func main() {
 //t1 := tree.New(1)
 //fmt.Println(t1)
 fmt.Println(Same(tree.New(1), tree.New(1)))
 fmt.Println(Same(tree.New(1), tree.New(2)))
}

 
Output:

true
false

Program exited.
 
Function Same, version 2:
 
func Same(t1, t2 *tree.Tree) (b_same bool) {
 c1 := make(chan int)
 c2 := make(chan int)
 b_same = true
 go func() {
  Walk(t1, c1)
  close(c1)
 }()
 go func() {
  Walk(t2, c2)
  close(c2)
 }()
 for {
  v1, ok1 := <-c1
  v2, ok2 := <-c2
  if !ok1 || !ok2 {
   return ok1 == ok2
  }
  if v1 != v2 {
   b_same = false
   break
  }
 }
 return
}
Ref:
http://tour.golang.org/concurrency/8
https://golang.org/doc/play/tree.go
https://github.com/golang/tour/blob/master/tree/tree.go
Post a Comment