Go语言之旅-练习-等价二叉查找树

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

type Tree Struct {
    Left *Tree
    Value int
    Right *Tree
}

实现Walk函数，来遍历一个二叉树的所有值，用Walk实现Same函数来检测两个二叉树是否存储了相同的值。

是否存储了相同的值表明这个问题与二叉树中值的顺序无关。

使用Go良好的Go程与Channel特性，可以减少一些中间变量，达到更好的性能。

代码实现

package main

import (
    "golang.org/x/tour/tree"
    "fmt"
    "sort"
)


func walkSub (t *tree.Tree, ch chan int) {
// 使用递归实现子树的遍历，并不去尝试关闭Channel
// 实际上也确实无法知道是不是该关闭
    ch <- t.Value
    if (t.Left != nil) {
        walkSub(t.Left, ch);
    }
    if (t.Right != nil) {
        walkSub(t.Right, ch);
    }
}
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk (t *tree.Tree, ch chan int) {
// 开始从树顶开始遍历树
// 最开始的想法是仅使用一个Walk函数
// 但是仔细想想，如果仅使用Walk，每个子树实际上缺少上下文来判断自己在不在树顶部
// 也就没法判断自己该不该关闭Channel了
// 而如果树的根节点的子树都遍历完了，就可以安全的关闭Channel了
    ch <- t.Value
    if(t.Left != nil) {
        walkSub(t.Left, ch);
    }
    if(t.Right != nil) {
        walkSub(t.Right, ch);
    }
    close(ch)
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same (t1, t2 *tree.Tree) bool {
    cht1 := make(chan int)
    cht2 := make(chan int)
    t1v := make([]int, 0)
    t2v := make([]int, 0)
    go Walk(t1, cht1)
    go Walk(t2, cht2)
// 将Channel的内容读入slice，方便之后的处理
    for w := range cht1 {
        t1v = append(t1v, w)
    }
// sort.Ints([]int) 升序排列一个[]int，以此消除遍历树时顺序带来的影响
    sort.Ints(t1v)
    for w := range cht2 {
        t2v = append(t2v, w)
    }
    sort.Ints(t2v)
    if(len(t1v) != len(t2v)) {
        return false;
    } else {
        for i := 0; i != len(t1v); i += 1 {
            if(t1v[i] != t2v[i]) {
                return false;
            }
        }
    }
    return true;
}

func main() {
// 使用tree.new(k)，会随机生成一个v包含值k, 2k, ..., 10k的树
// 显然应该是相同的
    switch i := Same(tree.New(10), tree.New(10)); i {
    case true: fmt.Println("True!");
    case false: fmt.Println("False!");
    }
}

总结

Go程与Channel编程是Go最与众不同的地方了，他方便到虽然Go有许多其他坑，但却无伤大雅。Channel通过一种Pipeline的方式很好的解决了线程之间的数据传输问题，Buffer机制也能很好的解决性能问题。其他语言并非无法实现这个特性，但在Go中，这个特性与语言自身完美结合，使用起来非常优雅。

题目描述与分析

代码实现

总结