练习 等价二叉查找树

问题

不同二叉树的叶节点上可以保存相同的值序列。例如,以下两个二叉树都保存了序列 `1,1,2,3,5,8,13`。


在大多数语言中,检查两个二叉树是否保存了相同序列的函数都相当复杂。 我们将使用 Go 的并发和信道来编写一个简单的解法。

本例使用了 tree 包,它定义了类型:

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}
1. 实现 Walk 函数。

2. 测试 Walk 函数。

函数 tree.New(k) 用于构造一个随机结构的已排序二叉查找树,它保存了值 k, 2k, 3k, ..., 10k。

创建一个新的信道 ch 并且对其进行步进:

go Walk(tree.New(1), ch)
然后从信道中读取并打印 10 个值。应当是数字 1, 2, 3, ..., 10。

3. 用 Walk 实现 Same 函数来检测 t1 和 t2 是否存储了相同的值。

4. 测试 Same 函数。

Same(tree.New(1), tree.New(1)) 应当返回 true,而 Same(tree.New(1), tree.New(2)) 应当返回 false。

Tree 的文档可在[这里](https://godoc.org/golang.org/x/tour/tree#Tree)找到。

背景知识

  1. 你需要了解什么是等价二叉树?
  2. 阅读Tree类型的Go实现源代码。代码实现了3个函数,New函数新建二叉树,insert函数插入新元素,实现了打印字符串String接口
  3. 了解协程,信道的实现原理。
  4. 判断等价二叉树相等的话,那么左右节点的值都需要相等。

实现思路

  1. 实现 Walk 函数,循环通过信道发送数据,然后接受并输出。Walk的遍历方式为中序遍历,先遍历根节点,然后左节点,最后右节点。
  2. 注意tree的遍历方式,也就是获得值的方式,实现一个私有的walk函数,签名和Walk一致,因为Tree类型较为简单,并不能直接判断循环的结束。故采用这样的方式,循环遍历到最后,t == nil时,关闭信道,不然会报错的。
  3. 实现 Same 函数,循环判断tree每一个值是否相等。难点在于,创建2个信道,去读取Walk返回的Tree的节点值。

实现代码

GitHub

参考链接

  1. 练习:等价二叉查找树
  2. 二叉查找树
  3. Go指南练习之《等价二叉树》(Equivalent Binary Trees)

发表评论

电子邮件地址不会被公开。 必填项已用*标注