使用 Channel 实现树的遍历

tree

在此处简单回顾一下之前学过的二叉树遍历，首先新建一个名为 tree 的目录，并在其下对文件和子目录进行如下组织：

其中 node.go 存放的是 Node 的定义：

package treeimport "fmt"type Node struct {Value       intLeft, Right *Node
}func (node Node) Print() {fmt.Print(node.Value, " ")
}func (node *Node) SetValue(value int) {if node == nil {fmt.Println("Setting Value to nil" +" node. Ignored.")return}node.Value = value
}func CreateNode(value int) *Node { return &Node{Value: value} }// 👆 构建 Node 的工厂函数, Golang 支持返回局部变量的地址

traverse.go 存放的是树的遍历方法，使用的方法是中序遍历，下例还将展示如何以函数作为中序遍历的参数在 Golang 当中实现在树的遍历过程中的某些结点行为（本例实现行为是，当遍历到某个结点时，将其打印出来）：

package treeimport "fmt"func (node *Node) Traverse() {node.TraverseFunc(func(n *Node) {n.Print()})fmt.Println()
}func (node *Node) TraverseFunc(f func(*Node)) {if node == nil {return}node.Left.TraverseFunc(f)f(node)node.Right.TraverseFunc(f)
}

最后，entry.go 建立了一棵树：

package mainimport ("fmt""learngo/tree"
)func main() {var root tree.Noderoot = tree.Node{Value: 3}root.Left = &tree.Node{}root.Right = &tree.Node{5, nil, nil}root.Right.Left = new(tree.Node)root.Left.Right = tree.CreateNode(2)root.Right.Left.SetValue(4)fmt.Print("In-order traversal: ")root.Traverse()
}

使用 Channel 统计最大的结点下标

此处我们实现一个最简单的 Channel 遍历树的应用，即统计最大的结点下标，在 traverse.go 当中编写如下函数：

// 👇 使用 Channel 来完成树的遍历
func (node *Node) TraverseWithChannel() chan *Node {// 调用 TraverseWithChannel 获得的返回值是 chan *Nodeout := make(chan *Node)go func() {node.TraverseFunc(func(node *Node) {out <- node})close(out)}()return out
}

函数的返回值是 chan *Node ，即一个类行为 *Node 的通道。函数体当中的行为如下：

首先使用 make 方法新建一个通道，之后开启协程，将结点的值写入到通道当中。完成写入之后使用 close 方法关闭通道。

协程启动之后将通道返回。

在 main 函数中添加以下片段进行验证：

c := root.TraverseWithChannel()
maxNode := 0 // 统计最大的结点数
for node := range c {			// 不断地接受来自 channel 的信息if node.Value > maxNode {maxNode = node.Value}
}
fmt.Println("Max Node Value:", maxNode)