67

ゴーツアーで同等のバイナリツリーの演習を解決しようとしています。これが私がしたことです。

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)すべての値が送信される前にチャネルが閉じられるため、 on を使用できませんWalk()(再帰のため)。

4

29 に答える 29

125

クロージャーを使用したエレガントなソリューションが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)
}
于 2012-09-01T03:18:16.490 に答える
32

Walk関数がそれ自体で再帰しない場合は、close（）を使用できます。つまり、ウォークは次のようになります。

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

walkRecurseは多かれ少なかれ現在のWalk関数ですが、walkRecurseで繰り返します。（または、Walkを反復的に書き直します-当然のことながら、より面倒です）このアプローチでは、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内のノードの数をカウントする必要があります。

于 2012-09-01T01:07:57.013 に答える
16

これが私が行った方法です。違いは、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)))
}
于 2016-11-10T18:15:26.680 に答える
0

開いているチャネルを放置しないようにする必要があります。そうしないと、スレッドが永遠に待機して終了しない可能性があります。

package main

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

func WalkRecurse(t *tree.Tree, ch chan int) {
    if t == nil {
        return
    }

    WalkRecurse(t.Left, ch)
    ch <- t.Value
    WalkRecurse(t.Right, ch)
}

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
    WalkRecurse(t, ch)
    close(ch)
}

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

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

        if ok1 != ok2 {
            ret = false
        }
        if ok1 && (v1 != v2) {
            ret = false
        }
        if !ok1 && !ok2 {
            break
        }
    }

    return ret
}

func main() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)
    for v := range ch {
        fmt.Print(v, " ")
    }
    fmt.Println()

    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
}
于 2015-01-19T02:05:56.763 に答える
0

質問はちょうど 10 ノードのツリーを言ったので、以下は他の回答を読んだ後の私の回答です：</p> 

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

    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)
}

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

    for range make([]struct{}, 10) {
        if <-ch1 != <-ch2 {
            return false
        }
    }
    return true
}
于 2016-09-10T02:56:58.317 に答える
0

異なるツリーの長さに依存せず、走査順序にも依存しないソリューションを次に示します。

package main

import (
    "fmt"
    "golang.org/x/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 walk func(*tree.Tree)
    walk = func(tr *tree.Tree) {
        if tr == nil {
            return
        }

        walk(tr.Left)
        ch <- tr.Value
        walk(tr.Right)
    }

    walk(t)
    close(ch)
}

func merge(ch chan int, m map[int]int) {
    for i := range ch {
        count, ok := m[i]
        if ok {
            m[i] = count + 1
        } else {
            m[i] = 1
        }
    }
}

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

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

    merge(ch1, m)
    merge(ch2, m)

    for _, count := range m {
        if count != 2 {
            return false
        }
    }

    return true
}
于 2016-09-23T07:19:11.157 に答える
0

私は常に両方のチャンネルを最後まで読む2つのバージョンを書きました:

package main

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

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)
}

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

    return sameChan(ch1, ch2)
}

func sameChan1(ch1, ch2 chan int) bool {
    areSame := true
    for {
        v1, ok1 := <-ch1
        v2, ok2 := <-ch2

        if !ok1 && !ok2 {
            return areSame
        }

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

func sameChan2(ch1, ch2 chan int) bool {
    areSame := true
    for v1 := range ch1 {
        v2, ok2 := <-ch2

        if !ok2 || v1 != v2 {
            areSame = false
        }
    }
    for _ = range ch2 {
        areSame = false
    }
    return areSame
}

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

    fmt.Println(Same(tree.New(1), tree.New(1), sameChan2))
    fmt.Println(Same(tree.New(2), tree.New(1), sameChan2))
    fmt.Println(Same(tree.New(1), tree.New(2), sameChan2))
}
于 2016-05-09T18:31:27.677 に答える
0

私のバージョン

package main


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

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

func Walk(t *tree.Tree, ch chan int) {
    WalkRec(t, ch)
    close(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 {
        x, okx := <-ch1
        y, oky := <-ch2
        switch {
        case okx != oky:
            return false
        case x != y:
            return false
        case okx == oky && okx == false:
            return true
        }

    }

}

func main() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)
    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(2), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
}
于 2016-03-21T14:26:57.243 に答える
0

自分のロジックで再帰呼び出しを使用しWalkていて、これ以上項目がないことをチャネル消費者に通知したい場合、自分のWalkロジックの大部分を 2 番目の関数に入れ、その 2 番目の関数を呼び出し、それが完了するのを待つことができるようです。 、次にチャネルを閉じます。

以下の例では、2 番目の ("inner Walk") 関数は、Walk関数内の直接の "クロージャー" ですが、そうである必要はありません。

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) {
    defer close(ch)
    var iw func(*tree.Tree)
    iw = func(it *tree.Tree) {
        if it == nil {
            return
        }
        iw(it.Left)
        ch <- it.Value
        iw(it.Right)
    }
    iw(t)
}

// 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 {
        v1, more1 := <- ch1
        v2, more2 := <- ch2
        if (!more1 && !more2) {
            return true
        }
        if more1 != more2 || v1 != v2 {
            return false
        }
    }
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(1)))
    fmt.Println(Same(tree.New(1), tree.New(2)))
}
于 2021-03-27T08:20:10.213 に答える
0

このスレでは今のところ見たことがない。func のためだけに提示された nil チャネル手法を使用しました

チャネルを閉じる際の問題は、ゴルーチン iife でチャネルを開始することで解決されました。

ただし、同等性についてはよりパフォーマンスを確認できると思います。

package main

import (
    "fmt"
    "reflect"
    "sort"

    "golang.org/x/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) {
    ch <- t.Value
    if t.Right != nil {
        Walk(t.Right, ch)
    }
    if t.Left != nil {
        Walk(t.Left, ch)
    }

}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {

    c1 := make(chan int)
    s1 := []int{}

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

    c2 := make(chan int)
    s2 := []int{}

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

    for c1 != nil || c2 != nil {
        select {
        case v, ok := <-c1:
            if !ok {
                c1 = nil
                sort.Ints(s1)
                continue
            }
            s1 = append(s1, v)
        case v, ok := <-c2:
            if !ok {
                c2 = nil
                sort.Ints(s2)
                continue
            }
            s2 = append(s2, v)
        }
    }
    return reflect.DeepEqual(s1, s2)
}

func main() {
    fmt.Println(Same(tree.New(1), tree.New(1)))
}
于 2020-06-03T19:21:18.130 に答える
0

deferこれが魔法のない私の解決策です。これは少し読みやすいと思ったので、共有する価値があります:)

おまけ: このバージョンでは、実際にツアーの演習の問題が解決され、適切な結果が得られます。

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) {
    walkRecursive(t, ch)
    close(ch)
}

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

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

    for i:= range ch1 {
        if i == <-ch2 {
            br = true
        } else {
            br = false
            break
        }
    }
    return br
}

func main() {
    ch := make(chan int)
    go Walk(tree.New(1), ch)

    for i := range ch {
        fmt.Println(i)
    }

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

したがって、出力は次のようになります。

1
2
3
4
5
6
7
8
9
10
false
true
false
于 2019-12-09T13:48:53.750 に答える
0

著者の場合、Same 関数を変更して無限ループを回避する必要があります。

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

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

    if <-ch1 != <-ch2 {
        return false
    }

    return true
}
于 2021-10-01T16:30:57.053 に答える
0

それが私が Inorder Traversal を使ってやった方法です

package main

import (
    "fmt"
    "golang.org/x/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) {
    if t != nil {
        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 {
    c1, c2 := make(chan int), make(chan int)
    go Walk(t1, c1)
    go Walk(t2, c2)
    if <-c1 == <-c2 {
        return true
    } else {
        return false
    }
}

func main() {
    t1 := tree.New(1)
    t2 := tree.New(8)
    fmt.Println("the two trees are same?", Same(t1, t2))
}
于 2016-06-22T15:30:42.630 に答える