练习 等价二叉查找树

问题

不同二叉树的叶节点上可以保存相同的值序列。例如,以下两个二叉树都保存了序列 `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)

练习 图像

问题

还记得之前编写的图片生成器吗?我们再来编写另外一个,不过这次它将会返回一个 image.Image 的实现而非一个数据切片。

定义你自己的 Image 类型,实现必要的方法并调用 pic.ShowImage。

Bounds 应当返回一个 image.Rectangle ,例如 image.Rect(0, 0, w, h)。

ColorModel 应当返回 color.RGBAModel。

At 应当返回一个颜色。上一个图片生成器的值 v 对应于此次的 color.RGBA{v, v, 255, 255}。

背景知识

这一次,我们需要更多的接口具体实现细节了。

1. 什么是图片生成器?
func main() {
    m := image.NewRGBA(image.Rect(0, 0, 100, 100))
    fmt.Println(m.Bounds())
    fmt.Println(m.At(0, 0).RGBA())
}

image接口类型
type Image interface {
    ColorModel() color.Model
    Bounds() Rectangle
    At(x, y int) color.Color
}

NewRGBA函数
func NewRGBA(r Rectangle) *RGBA {
    w, h := r.Dx(), r.Dy()
    buf := make([]uint8, 4*w*h)
    return &RGBA{buf, 4 * w, r}
}

2. 查看image包的源代码以及image/color的源代码。

实现思路

  1. 需要实现Image类型的三个指定接口。
  2. 第一个接口直接返回color.RGBAModel
  3. 第二个接口,需要初始化部分变量。
  4. 第三个接口,部分变量做算法计算,赋值给color.RGBA

实现代码

GitHub

参考链接

  1. 练习:图像

练习 rot13Reader

问题

有种常见的模式是一个 io.Reader 包装另一个 io.Reader,然后通过某种方式修改其数据流。

例如,gzip.NewReader 函数接受一个 io.Reader(已压缩的数据流)并返回一个同样实现了 io.Reader 的 *gzip.Reader(解压后的数据流)。

编写一个实现了 io.Reader 并从另一个 io.Reader 中读取数据的 rot13Reader,通过应用 rot13 代换密码对数据流进行修改。

rot13Reader 类型已经提供。实现 Read 方法以满足 io.Reader。

背景知识

  1. 首先你需要了解io.Reader接口详细实现。
type Reader interface {
    Read(p []byte) (n int, err error)
}
//这里定义Reader接口,需要实现一个Read函数、方法,参数为数组 返回为字节数和错误值。
type error interface {
    Error() string
}
//错误的接口实现
  1. gzip.NewReader的实现可以帮助你快速实现下面的练习。
type Reader struct {
    Header       // valid after NewReader or Reader.Reset
    r            flate.Reader
    decompressor io.ReadCloser
    digest       uint32 // CRC-32, IEEE polynomial (section 8)
    size         uint32 // Uncompressed size (section 2.3.1)
    buf          [512]byte
    err          error
    multistream  bool
}
func NewReader(r io.Reader) (*Reader, error) {
    z := new(Reader)
    if err := z.Reset(r); err != nil {
        return nil, err
    }
    return z, nil
}
//gzip的NewReader实现
  1. 你需要了解rot13算法的实现。
//直接从golang源代码里面copy就好了。路径为go/src/bytes/bytes_test.go 974行
func rot13(r rune) rune {
    const step = 13
    if r >= 'a' && r <= 'z' {
        return ((r - 'a' + step) % 26) + 'a'
    }
    if r >= 'A' && r <= 'Z' {
        return ((r - 'A' + step) % 26) + 'A'
    }
    return r
}
//这里找到算法,并不能实现,需要参数为[]byte的实现方案。
func rot13(b byte) byte {
    var a byte
    switch {
    case b >= 'a' && b <= 'z':
        a = 'a'
    case b >= 'A' && b <= 'Z':
        a = 'A'
    default:
        return b
    }
    return (b-a+13)%26 + a
}

  1. 获取变量的类型
Using string formatting
func typeof(v interface{}) string {
    return fmt.Sprintf("%T", v)
}
Using reflect package

func typeof(v interface{}) string {
    return reflect.TypeOf(v).String()
}
Using type assertions

func typeof(v interface{}) string {
    switch v.(type) {
    case int:
        return "int"
    case float64:
        return "float64"
    //... etc
    default:
        return "unknown"
    }
}

实现思路

  1. 定义错误类,溢出
  2. 实现Read接口
  3. 实现rot13算法
  4. 逻辑实现先判断异常情况,返回对应的错误信息
  5. 正常就返回读取的字节数和nil
  6. 这里需要注意的r.r.Read这个调用,第一个r是类型rot13Reader,它的结构体有一个成员r,类型为io.Reader,这个接口只有一个方法Read.

实现代码

GitHub

参考链接

  1. 练习:rot13Reader
  2. rot13 加密
  3. How to find a type of an object in Go?