Using goroutine to compare two trees in Golang are equivalent

php editor Banana introduced that Golang is a powerful programming language, and goroutine is one of its important features of concurrent programming. In Golang, we often need to compare the equivalence of two trees, that is, to determine whether two trees have the same structure and value. Using goroutine to perform tree comparison operations can improve program efficiency and concurrency performance. By performing a recursive comparison of the nodes of two trees in parallel, the comparison time can be significantly reduced. This method is not only simple and efficient, but also easy to understand and implement. Therefore, using goroutine to compare two trees in Golang is a recommended approach.

Question content

Without using channels I can compare two trees to see if they are equivalent, but with channels I can't figure out how to do that.

This is the sample code I wrote using channels.

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

func Same(t1, t2 *Tree) bool {

    t1Ch := make(chan int)
    t2Ch := make(chan int)

    Walk(t1, t1Ch)
    Walk(t2, t2Ch)
    output := make(chan bool)
    go func() {
        n1 := <-t1Ch
        n2 := <-t2Ch
        output <- n1 == n2
    }()
    return <-output

}

func main() {
    fmt.Println((&root, &root1))
}

Note:: You can find the full description here https://go.dev/tour/concurrency/7

Workaround

First, you should complete the tree walk Then close the channel. This can be done by detaching the recursive function as follows:

func walk(t *tree.tree, ch chan int) {
    defer close(ch)
    if t != nil {
        ch <- t.value
        walkrecursively(t.left, ch)
        walkrecursively(t.right, ch)
    }
    
}

func walkrecursively(t *tree.tree, ch chan int) {
    if t != nil {
        ch <- t.value
        walkrecursively(t.left, ch)
        walkrecursively(t.right, ch)
    }
}

Now your same() function can cover both channels and know when the work is complete:

func same(t1, t2 *tree.tree) bool {

    // two channels for walking over two trees
    ch1 := make(chan int)
    ch2 := make(chan int)
    
    // two integer slices to capture two results
    sequence1 := []int{}
    sequence2 := []int{}
    
    // two go routines to push values to the channels
    // important! these must be go routines
    go walk(t1, ch1)
    go walk(t2, ch2)
    
    // range over the channels to populate the sequence vars
    for n1 := range ch1 {
        sequence1 = append(sequence1, n1)   
    }
    for n2 := range ch2 {
        sequence2 = append(sequence2, n2)   
    }

    // since trees are randomly structured, we sort
    sort.ints(sequence1)
    sort.ints(sequence2)

    // slicesareequal is a helper function
    return slicesareequal(sequence1, sequence2)
}

Your helper function might look like this:

func slicesAreEqual(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }
    return true
}

The above is the detailed content of Using goroutine to compare two trees in Golang are equivalent. For more information, please follow other related articles on the PHP Chinese website!