php小编香蕉介绍,Golang是一门强大的编程语言,而goroutine是其并发编程的重要特性之一。在Golang中,我们经常需要比较两个树的等价性,即判断两棵树是否具有相同的结构和数值。使用goroutine来进行树的比较操作可以提高程序的效率和并发性能。通过并行地对两棵树的节点进行递归比较,可以显著缩短比较的时间。这种方式不仅简洁高效,而且易于理解和实现。因此,使用goroutine来比较Golang中的两棵树是一种值得推荐的方法。
问题内容
如果不使用通道,我可以比较两棵树是否等效,但使用通道时,我无法弄清楚该怎么做。
这是我使用通道编写的示例代码。
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))
}
注意:: 你可以在这里找到完整的描述 https://go.dev/tour/concurrency/7
解决方法
首先,您应该在完成树的行走后关闭通道。这可以通过分离递归函数来完成,如下所示:
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)
}
}
现在您的 same() 函数可以覆盖两个通道并知道工作何时完成:
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)
}
您的辅助函数可能如下所示:
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
}