Go Tour Упражнение: эквивалентные двоичные деревья

Я пытаюсь решить эквивалентные бинарные деревья упражнение на гастроли. Вот что я сделал;

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() потому что он закрывает канал перед отправкой всех значений (из-за рекурсии). Кто-нибудь может мне помочь?

Ответы

Ответ 1

Вы можете использовать close(), если ваша функция Walk не работает сама по себе. т.е. иди бы просто сделал:

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

Ответ 2

Элегантное решение с помощью закрытия было представлено в golang орехов группы,

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

Ответ 3

Здесь полное решение, использующее идеи здесь и из Группа Google

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

}

Ответ 4

Вот как я это сделал, разница в том, что вы можете обернуть 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)))
}

Ответ 5

В этом решении я придумал:

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

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

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

    for i:=range ch {
        j,ok:=<-dh
        if(i!=j||!ok)  {return false} 
    }

    return true
}

Ответ 6

Это мое решение. Он правильно проверяет различия в длине двух последовательностей.

package main

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

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

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

    go Walk(t1, chana)
    go Walk(t2, chanb)

    for {
        n1, ok1 := <-chana
        n2, ok2 := <-chanb        
        if n1 != n2 || ok1 != ok2 {
            return false
        }
        if (!ok1) {
            break
        }
    }
    return true; 
}

Ответ 7

Вы получили это почти правильно, нет необходимости использовать оператор select, потому что вы слишком часто будете проходить через событие default, здесь мое решение работает без необходимости подсчета количества узлов в tress:

func Same(t1, t2 *tree.Tree) bool {
    ch1, ch2 := make(chan int), make(chan int)
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    for i := range ch1 {
        j, more := <-ch2
        if more {
            if i != j { return false }
        } else { return false }
    }

    return true
}

Ответ 8

Хотя моей первой интуицией было также завернуть рекурсивную прогулку и закрыть каналы, я чувствовал, что это не в духе упражнения.

Текст упражнения содержит следующую информацию:

Функция 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)))
}

Если бы целью было бегать по деревьям произвольного размера, то лучше всего было бы реагировать на закрытые каналы, но я чувствовал, что это было простое упражнение с намеренно наложенными ограничениями, чтобы облегчить жизнь новому суслику.

Ответ 9

Попытался решить эту проблему, используя структуру карты.

func Same(t1, t2 *tree.Tree) bool {
    countMap := make(map[int]int)
    ch := make(chan int)
    go Walk(t1, ch)
    for v := range ch {
        countMap[v]++
    }
    ch = make(chan int)
    go Walk(t2, ch)
    for v := range ch {
        countMap[v]--
        if countMap[v] < 0 {
            return false
        }
    }
    return true
}

Ответ 10

Все предыдущие ответы не решают задачу о Same функции. Вопрос в том:

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

Это не должно учитывать структуру дерева. Вот почему следующие тесты терпят неудачу, дает нам false в обеих строках:

fmt.Println("Should return true:", Same(tree.New(1), tree.New(1)))
fmt.Println("Should return false:", Same(tree.New(1), tree.New(2)))

Помните?

Функция tree.New(k) создает случайно структурированное (но всегда отсортированное) двоичное дерево, содержащее значения k, 2k, 3k,..., 10k.

Вам просто нужно убедиться, что оба дерева имеют одинаковые значения. И в описании задачи четко заметили, что:

Same(tree.New(1), tree.New(1)) должна возвращать true, а Same(tree.New(1), tree.New(2)) должна возвращать false.

Таким образом, для решения этой задачи вам нужно буферизовать все результаты из одного дерева и проверить, находятся ли значения из второго дерева в первом.

Вот мое решение, оно не идеальное :)

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

    var tv1 = []int{}

    for v := range ch1 {
        tv1 = append(tv1, v)
    }

    inArray := func(arr []int, value int) bool {
        for a := range arr {
            if arr[a] == value {
                return true
            }
        }
        return false
    }

    for v2 := range ch2 {
        if !inArray(tv1, v2) {
            return false
        }
    }

    return true
}

Ответ 11

Вам следует избегать открытия открытых каналов без присмотра или нить может ждать всегда и никогда не заканчиваться.

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

Ответ 12

Моя версия

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

Ответ 13

Я написал 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))
}

Ответ 14

Вот как я это сделал с помощью 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))
}

Ответ 15

потому что вопрос просто сказал, что дерево всего 10 узлов, а затем мой ответ после прочтения других ответов:

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
}

Ответ 16

Здесь решение, которое не зависит от разной длины дерева и не зависит от порядка обхода:

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
}

Ответ 17

Для тех, кто заинтересован, если вам интересно, как решить эту проблему без создания отдельной рекурсивной функции, вот ответ с использованием стека:

func Walk(t *tree.Tree, ch chan int) {
    defer close(ch)
    visitStack := []*tree.Tree{t}
    visited := make(map[*tree.Tree]bool, 1)
    for len(visitStack) > 0 {
        var n *tree.Tree
        n, visitStack = visitStack[len(visitStack)-1], visitStack[:len(visitStack)-1]
        if visited[n] {
            ch <- n.Value
            continue
        }
        if n.Right != nil {
            visitStack = append(visitStack, n.Right)
        }
        visitStack = append(visitStack, n)
        if n.Left != nil {
            visitStack = append(visitStack, n.Left)
        }
        visited[n] = true
    }
}

Ответ 18

Четкий ответ:

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 {
        return
    }
    Walk(t.Left, ch)
    ch <- t.Value
    Walk(t.Right, ch)
}

func WalkATree(t *tree.Tree, ch chan int) {
    Walk(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 WalkATree(t1, ch1)
    go WalkATree(t2, ch2)
    var v1, v2 int
    var ok1, ok2 bool
    for {
        v1, ok1 = <- ch1
        v2, ok2 = <- ch2
        if !ok1 && !ok2 {
            return true
        }
        if !ok1 && ok2 || ok1 && !ok2 {
            return false
        }
        if v1 != v2 {
            return false
        }
    }
}

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