游览练习:等效二叉树

Question

我正试图在旅行中解决等效的二叉树运动.这就是我所做的;

package main

import "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.Left != nil {
        Walk(t.Left, ch)
    }
    ch <- 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) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for k := range ch1 {
        select {
        case g := <-ch2:
            if k != g {
                return false
            }
        default:
            break
        }
    }
    return true
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
}

但是,我无法找到如何在树木中留下更多元素的信号.我无法使用close(ch),Walk()因为它会在所有值发送之前使通道关闭(因为递归).任何人都可以借给我一个手吗？

Answer 1

使用闭合的优雅解决方案在golang-nuts组中呈现,

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch) // <- closes the channel when this function returns
    var walk func(t *tree.Tree)
    walk = func(t *tree.Tree) {
        if t == nil {
            return
        }
        walk(t.Left)
        ch <- t.Value
        walk(t.Right)
    }
    walk(t)
}

Answer 2

以下是使用此处和Google Group主题提供的完整解决方案

package main

import "fmt"
import "code.google.com/p/go-tour/tree"

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

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1, ch2 := make(chan int), make(chan int)

    go Walk(t1, ch1)
    go Walk(t2, ch2)

    for {
        v1,ok1 := <- ch1
        v2,ok2 := <- ch2

        if v1 != v2 || ok1 != ok2 {
            return false
        }

        if !ok1 {
            break
        }
    }

    return true
}

func main() {
    fmt.Println("1 and 1 same: ", Same(tree.New(1), tree.New(1)))
    fmt.Println("1 and 2 same: ", Same(tree.New(1), tree.New(2)))

}

Answer 3

如果您的Walk函数本身没有递归,您可以使用close().即步行只会做:

func Walk(t *tree.Tree, ch chan int) {
    walkRecurse(t, ch)
    close(ch)
}

walkRecurse或多或少是你当前的Walk函数,但是在walkRecurse上递归.(或者你重写Walk是迭代的 - 授予,更多是hazzle)使用这种方法,你的Same()函数必须知道通道是关闭的,这是通过表单的通道接收来完成的

k, ok1 := <-ch
g, ok2 := <-ch

并采取适当的时候采取行动ok1,并ok2是不同的,或者当他们都false

另一种方法,但可能不是在练习的精神,是计算树中节点的数量:

func Same(t1, t2 *tree.Tree) bool {
    countT1 := countTreeNodes(t1)
    countT2 := countTreeNodes(t2)
    if countT1 != countT2 {
        return false
    }
    ch1 := make(chan int)
    ch2 := make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for i := 0; i < countT1; i++ {
        if <-ch1 != <-ch2 {
            return false
        }
    }
    return true
}

您必须实现countTreeNodes()函数,该函数应计算*Tree中的节点数

Answer 4

虽然我的第一直觉是也结束递归遍历并关闭通道，但我觉得这不符合练习的精神。

练习文本包含以下信息：

该函数tree.New(k)构造一个随机结构（但始终排序）的二叉树，其中包含值k, 2k, 3k, ..., 10k。

其中清楚地表明生成的树恰好有 10 个节点。

因此，本着本练习的精神和简单性，我采用了以下解决方案：

package main

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

func Walk(t *tree.Tree, ch chan int) {
    if t.Left != nil {
        Walk(t.Left, ch)
    }
    ch <- t.Value
    if t.Right != nil {
        Walk(t.Right, ch)
    }
}

func Same(t1, t2 *tree.Tree) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)

    defer close(ch1)
    defer close(ch2)

    go Walk(t1, ch1)
    go Walk(t2, ch2)

    for i := 0; i < 10; i++ {
        if <-ch1 != <-ch2 {
            return false
        }
    }

    return true
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(2)))
}

如果目标是在任意大小的树上运行，那么对封闭通道做出反应是更好的解决方案，但我觉得这是一个简单的练习，有意设置限制，以使新的 Gopher 更容易。

Answer 5

这是我的解决方案。

package main

import (
  "golang.org/x/tour/tree"
  "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 {
        return
    }
    
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1,ch2 := make(chan int),make(chan int)
    
    go func() {
        Walk(t1, ch1)
        close(ch1)
    }()
    
    go func() {
        Walk(t2, ch2)
        close(ch2)
    }()
    
    for {
        v1, ok1 := <- ch1
        v2, ok2 := <- ch2
        
        if ok1 == false && ok2 == false {
            return true
        }
        
        if v1 != v2 {
            return false
        }
    }

    return false
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(1))) 
    fmt.Println(Same(tree.New(1), tree.New(2))) 
}

Answer 6

这就是我做的方式,区别在于你可以将其包装Walk到匿名函数中并defer close(ch)在其中.因此,您不必定义其他命名的递归函数

package main

import (
    "golang.org/x/tour/tree"
    "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 {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
    ch1, ch2 := make(chan int), make(chan int)
    go func() {
        defer close(ch1)
        Walk(t1, ch1)
    }()
    go func() {
        defer close(ch2)
        Walk(t2, ch2)
    }()
    for {
        v1, ok1 := <- ch1
        v2, ok2 := <- ch2
        if ok1 != ok2 || v1 != v2 {
            return false
        }
        if !ok1 && !ok2 {
            break
        }
    }
    return true
}

func main() {
    ch := make(chan int)
    go func () {
        defer close(ch)
        Walk(tree.New(3), ch)
    }()
    for i := range ch {
        fmt.Println(i)
    }

    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
    fmt.Println(Same(tree.New(10), tree.New(10)))
}

Answer 7

将 goroutine 与匿名函数一起使用

go func() {
    .... // logic
    close(ch)// last close channel or defer close channel
    // do not use close() outside of goroutine
}()

这是可以轻松阅读的代码

步行功能

func Walk(t *tree.Tree, ch chan int) {
    if t.Left != nil {
        Walk(t.Left, ch)
    }
    ch <- t.Value
    if t.Right != nil {
        Walk(t.Right, ch)
    }
}

相同的功能

func Same(t1, t2 *tree.Tree) bool {
    ch1 := make(chan int)
    ch2 := make(chan int)

    go func() {
        Walk(t1, ch1)
        close(ch1)
        }()
    }()


    go func() {
        Walk(t2, ch2)
        close(ch2)
        }()
    }()

    for {
        v1, ok1 := <- ch1
        v2, ok2 := <- ch2
    
        if !ok1 && !ok2 {
            // both closed at the same time (and all values until now were equal)
            return true
        }
    
        if !ok1 || !ok2 || v1 != v2 {
            return false
        }
    }
    return true
}

主要功能

func main() {
    c := make(chan int)
    t1 := tree.New(1)
    go func() {
        Walk(t1, c)
        close(c)
    }()

    for i := range c {
        fmt.Print(i) // 12345678910
    }

    fmt.Println("")
    result1 := Same(tree.New(1), tree.New(1))
    fmt.Println(result1) // true
    result2 := Same(tree.New(1), tree.New(2))
    fmt.Println(result2) // false
}