Go 并发实战：使用通道检查二叉树等价性
前言
在大多数编程语言中，检查两棵二叉树是否存储相同的值序列是一个相当复杂的问题。通常需要编写递归算法来遍历两棵树，然后逐节点比较。但在 Go 语言中，我们可以利用其强大的并发原语和通道（channel）机制，写出简洁优雅的解决方案。
本文将通过 Go Tour 的一个经典练习，展示如何使用 Go 的并发特性来解决二叉树等价性问题。
问题描述
给定两棵二叉树，如何判断它们是否包含相同的值序列？注意，这里不要求树的结构完全相同，只要中序遍历的结果相同即可。
例如，以下两棵不同的二叉树都存储了序列 1, 1, 2, 3, 5, 8, 13：
树1 树2
8 5
/ \ / \
3 13 2 8
/ \ / / \
1 5 1 3 13
/
1
传统的解决方案需要：
1. 分别对两棵树进行中序遍历，将结果存储到数组中
2. 比较两个数组是否相等
这种方法需要额外的存储空间，且代码较为冗长。让我们看看 Go 如何用更优雅的方式解决这个问题。
核心概念：Go 的通道（Channel）
在开始实现之前，先回顾一下 Go 通道的关键特性：
– 通道是类型安全的队列：chan int 表示一个整数类型的通道
– 发送和接收操作：ch <- value 发送值，value := <-ch 接收值
- 阻塞特性：发送和接收操作会阻塞，直到另一方准备好
- 可关闭：使用 close(ch) 关闭通道，接收方可以通过 value, ok := <-ch 检测通道是否关闭
- 与 goroutine 配合：通道是 goroutine 之间通信的主要方式
实现步骤
第一步：实现 Walk 函数
Walk 函数的任务是中序遍历二叉树，并将每个节点的值发送到通道中。
// Walk 中序遍历树 t，将所有值发送到通道 ch
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
// 递归遍历左子树
Walk(t.Left, ch)
// 发送当前节点的值
ch <- t.Value
// 递归遍历右子树
Walk(t.Right, ch)
}
// Walk 中序遍历树 t，将所有值发送到通道 ch
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
// 递归遍历左子树
Walk(t.Left, ch)
// 发送当前节点的值
ch <- t.Value
// 递归遍历右子树
Walk(t.Right, ch)
}
关键点解析：
1. 中序遍历：按照”左子树 → 根节点 → 右子树”的顺序遍历，这样对于排序二叉树，输出的值会是升序的
2. 递归结构：每次递归都会将值发送到同一个通道，保证值的顺序性
3. 阻塞发送：ch <- t.Value 是阻塞操作，只有当有接收方准备好接收时才会继续执行
第二步：测试 Walk 函数
在实现 Same 函数之前，我们先测试 Walk 是否正常工作。
func main() {
// 测试 Walk 函数
fmt.Println("测试 Walk 函数:")
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
fmt.Print(<-ch, " ")
}
fmt.Println()
}
说明：
– tree.New(k)创建一个随机结构的排序二叉树，包含值 k, 2k, 3k, …, 10k
– 使用 go Walk(…) 在独立的 goroutine 中执行遍历，避免阻塞主线程
– 从通道中读取 10 个值，应该输出 1 2 3 4 5 6 7 8 9 10
第三步：实现 Same 函数
这是整个练习的核心。我们需要利用 Walk 函数来判断两棵树是否等价。
// Same 判断树 t1 和 t2 是否包含相同的值
func Same(t1, t2 *tree.Tree) bool {
// 创建两个通道
ch1 := make(chan int)
ch2 := make(chan int)
// 启动两个 goroutine 分别遍历两棵树
go func() {
Walk(t1, ch1)
close(ch1)
}()
go func() {
Walk(t2, ch2)
close(ch2)
}()
// 同时从两个通道读取值并比较
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 如果两个通道都关闭了，说明遍历完成且所有值都相等
if !ok1 && !ok2 {
return true
}
// 如果一个通道关闭而另一个没有，或者值不相等，返回 false
if !ok1 || !ok2 || v1 != v2 {
return false
}
}
}
设计思路：
1. 并行遍历：启动两个 goroutine 分别遍历两棵树，充分利用并发能力
2. 及时关闭通道：每个 goroutine 在完成遍历后关闭自己的通道，让接收方知道遍历结束
3. 同步比较：在主 goroutine 中同时从两个通道读取值，实现”边遍历边比较”的效果
4. 提前终止：一旦发现不相等的值或长度不一致，立即返回 false，无需遍历完整棵树
比较逻辑详解：
v1, ok1 := <-ch1
v2, ok2 := <-ch2
– ok1 和 ok2 表示通道是否仍然开放
– 如果 !ok1 && !ok2：两个通道都关闭，说明两棵树的节点数相同且所有值都相等
– 如果 !ok1 || !ok2：一个通道先关闭，说明两棵树的节点数不同
– 如果 v1 != v2：当前节点的值不相等
第四步：测试 Same 函数
func main() {
// ... 前面的 Walk 测试代码 ...
// 测试 Same 函数
fmt.Println("\n测试 Same 函数:")
fmt.Println("Same(tree.New(1), tree.New(1)) =", Same(tree.New(1), tree.New(1)))
fmt.Println("Same(tree.New(1), tree.New(2)) =", Same(tree.New(1), tree.New(2)))
}
预期输出：
Same(tree.New(1), tree.New(1)) = true
Same(tree.New(1), tree.New(2)) = false
完整代码
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk 中序遍历树 t，将所有值发送到通道 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 判断树 t1 和 t2 是否包含相同的值
func Same(t1, t2 *tree.Tree) bool {
// 创建两个通道用于接收树的值
ch1 := make(chan int)
ch2 := make(chan int)
// 启动两个 goroutine 分别遍历两棵树
go func() {
Walk(t1, ch1)
close(ch1) // 关闭通道，表示遍历完成
}()
go func() {
Walk(t2, ch2)
close(ch2) // 关闭通道，表示遍历完成
}()
// 同时从两个通道读取值并比较
for {
v1, ok1 := <-ch1
v2, ok2 := <-ch2
// 如果两个通道都关闭了，说明遍历完成且所有值都相等
if !ok1 && !ok2 {
return true
}
// 如果一个通道关闭而另一个没有，或者值不相等，返回 false
if ok1 != ok2 || v1 != v2 {
return false
}
}
}
func main() {
// 测试 Walk 函数
fmt.Println("测试 Walk 函数：")
ch := make(chan int)
go Walk(tree.New(1), ch)
for i := 0; i < 10; i++ {
fmt.Print(<-ch, " ")
}
fmt.Println()
// 测试 Same 函数
fmt.Println("\n测试 Same 函数：")
fmt.Println("Same(tree.New(1), tree.New(1)) =", Same(tree.New(1), tree.New(1)))
fmt.Println("Same(tree.New(1), tree.New(2)) =", Same(tree.New(1), tree.New(2)))
}
为什么这个方案更优雅？
1. 无需额外存储
传统方法需要将遍历结果存储到数组中，而这个方案直接在遍历过程中进行比较，节省了内存空间。
2. 惰性求值
由于通道的阻塞特性，我们实际上是”按需”获取值。一旦发现问题就可以提前终止，不需要遍历整棵树。
3. 天然并行
两棵树的遍历可以同时进行，充分利用多核 CPU 的优势。
4. 代码简洁
整个解决方案只需要约 40 行代码，逻辑清晰，易于理解。
深入思考
性能分析
虽然这个方案使用了并发，但需要注意：
– 通道操作的开销：每次发送和接收都有同步开销
– goroutine 的创建成本：创建 goroutine 虽然轻量，但也有成本
– 适用场景：对于小型树，传统方法可能更快；对于大型树或需要流式处理的场景，这个方案更有优势
改进方向
1. 使用缓冲通道`make(chan int, bufferSize) 可以减少阻塞次数，提高性能
2. 添加超时机制：防止某棵树的遍历陷入死循环
3. 支持泛型：Go 1.18+ 可以使用泛型支持不同类型的树
总结
通过这个练习，我们学习了：
1. ✅ 如何使用通道在 goroutine 之间传递数据
2. ✅ 如何利用通道的阻塞特性实现同步
3. ✅ 如何通过关闭通道来信号化任务的完成
4. ✅ 如何将并发思维应用到算法设计中
Go 的并发模型（CSP – Communicating Sequential Processes）让我们能够以声明式的方式编写并发代码，避免了传统多线程编程中的锁、条件变量等复杂机制。”不要通过共享内存来通信，而要通过通信来共享内存” —— 这正是 Go 并发哲学的精髓。
测试一下，缓存功能哈。