43. 等价二叉树 | 厚土Go学习笔记

实现两个二叉树的比较。二叉树的基本类型和函数来源于 “golang.org/x/tour/tree”,为了避免网络问题影响代码运行,我把源码直接加入到了代码中。

// A Tree is a binary tree with integer values.
type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

// New returns a new, random binary tree holding the values k, 2k, ..., 10k.
func New(k int) *Tree {
    var t *Tree
    for _, v := range rand.Perm(10) {

        t = insert(t, (1+v)*k)
    }
    return t
}

func insert(t *Tree, v int) *Tree {
    if t == nil {
        return &Tree{nil, v, nil}
    }
    if v < t.Value {
        t.Left = insert(t.Left, v)
    } else {
        t.Right = insert(t.Right, v)
    }
    return t
}

func (t *Tree) String() string {
    if t == nil {
        return "()"
    }
    s := ""
    if t.Left != nil {
        s += t.Left.String() + " "
    }
    s += fmt.Sprint(t.Value)
    if t.Right != nil {
        s += " " + t.Right.String()
    }
    return "(" + s + ")"
}

以上代码实现了二叉树的基本功能。下面我们来实现二叉树的比较。

要比较两个二叉树是否一致。我们建立一个函数。Same(t1, t2 *Tree) bool

为了比较二叉树,必要把二叉树的值放进一个通道中。共使用两个通道来进行比较。放入通道中的函数我们建立为 Walk(t *Tree, ch chan int) 同时再建立一个递归函数,用来遍历二叉树所有的叶子节点 rangeTree(t *Tree, ch chan int)

//遍历二叉树,把当前节点值传入通道
func rangeTree(t *Tree, ch chan int)  {
    if t != nil{
        rangeTree(t.Left, ch)
        ch <- t.Value
        rangeTree(t.Right, ch)
    }
}
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *Tree, ch chan int){
    rangeTree(t, ch)
    close(ch)
}
// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *Tree) bool{
    //建立两个通道
    ch1 := make(chan int)
    ch2 := make(chan int)
    //遍历两个二叉树,把值传入各自的通道
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    //遍历通道进行比较,有不同的值就返回false
    for i := range ch1{
        if i != <- ch2{
            return false
        }
    }
    return true
}

然后在 main函数中比较两个 tree

fmt.Println(Same(New(1), New(1)))
fmt.Println(Same(New(1), New(2)))

完整代码示例

package main

import (
    "fmt"
    "math/rand"
)
// A Tree is a binary tree with integer values.
type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

// New returns a new, random binary tree holding the values k, 2k, ..., 10k.
func New(k int) *Tree {
    var t *Tree
    for _, v := range rand.Perm(10) {

        t = insert(t, (1+v)*k)
    }
    return t
}

func insert(t *Tree, v int) *Tree {
    if t == nil {
        return &Tree{nil, v, nil}
    }
    if v < t.Value {
        t.Left = insert(t.Left, v)
    } else {
        t.Right = insert(t.Right, v)
    }
    return t
}

func (t *Tree) String() string {
    if t == nil {
        return "()"
    }
    s := ""
    if t.Left != nil {
        s += t.Left.String() + " "
    }
    s += fmt.Sprint(t.Value)
    if t.Right != nil {
        s += " " + t.Right.String()
    }
    return "(" + s + ")"
}

// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *Tree, ch chan int){
    rangeTree(t, ch)
    close(ch)
}
//遍历二叉树,把当前节点值传入通道
func rangeTree(t *Tree, ch chan int)  {
    if t != nil{
        rangeTree(t.Left, ch)
        ch <- t.Value
        rangeTree(t.Right, ch)
    }
}

// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *Tree) bool{
    //建立两个通道
    ch1 := make(chan int)
    ch2 := make(chan int)
    //遍历两个二叉树,把值传入各自的通道
    go Walk(t1, ch1)
    go Walk(t2, ch2)
    //遍历通道进行比较,有不同的值就返回false
    for i := range ch1{
        if i != <- ch2{
            return false
        }
    }
    return true
}

func main() {
    fmt.Println("二叉树遍历比较")
    fmt.Println("打印 New(1)的值")
    //打印 New(1)的值
    var ch1 = make(chan int)
    go Walk(New(1), ch1)
    for v := range ch1{
        fmt.Println(v)
    }
    fmt.Println("打印 New(2)的值")
    //打印 New(2)的值
    var ch2  = make(chan int)
    go Walk(New(2), ch2)
    for v := range ch2{
        fmt.Println(v)
    }
    //比较两个tree的值是否相等
    fmt.Println(Same(New(1), New(1)))
    fmt.Println(Same(New(1), New(2)))
}

运行结果

二叉树遍历比较
打印 New(1)的值
1
2
3
4
5
6
7
8
9
10
打印 New(2)的值
2
4
6
8
10
12
14
16
18
20
true
false

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2018-02-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

39450
来自专栏数据处理

leetcode222求完全二叉树节点个数

38640
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

33580
来自专栏高性能服务器开发

算法导论第十三章 红黑树(2)

这一章我觉得难点就在于删除修复,插入修复是比较容易想到的,然后我认为需要着重注意的地方都记录下来了,下面贴上自己写的基于C++模板的代码,有点长。...

10220
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

11720
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

10940
来自专栏Golang语言社区

go语言mongdb管道使用(二)

原始代码: /* 重点项目实体机需求汇总 查询数据 */ func (this *IndexController) ProjectReqTotalData(...

34970
来自专栏前端迷

数据结构与前端开发(四)-树

二叉树拥有一个根节点,每个节点至多拥有两个子节点,分别为:左节点和右节点。树的最底部节点称之为叶节点,当一颗树的叶数量数量为满时,该树可以称之为满二叉树。

22330
来自专栏大史住在大前端

野生前端的数据结构基础练习(7)——二叉树

一棵树最上面的点称为根节点,如果一个节点下面连接多个节点,那么该节点称为父节点,下面的节点称为子节点,二叉树的每一个节点最多有2个子节点,一个节点子节点的个数称...

10320
来自专栏Java爬坑系列

【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

  TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

11320

扫码关注云+社区

领取腾讯云代金券