本文实例讲述了Go语言实现的树形结构数据比较算法。分享给大家供大家参考。具体实现方法如下:
复制代码 代码如下:
// Two binary trees may be of different shapes,
// but have the same contents. For example:
//
// 4 6
// 2 6 4 7
// 1 3 5 7 2 5
// 1 3
//
// Go's concurrency primitives make it easy to
// traverse and compare the contents of two trees
// in parallel.
package main
import (
"fmt"
"rand"
)
// A Tree is a binary tree with integer values.
type Tree struct {
Left *Tree
Value int
Right *Tree
}
// Walk traverses a tree depth-first,
// sending each Value on a channel.
func Walk(t *Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
// Walker launches Walk in a new goroutine,
// and returns a read-only channel of values.
func Walker(t *Tree) <-chan int {
ch := make(chan int)
go func() {
Walk(t, ch)
close(ch)
}()
return ch
}
// Compare reads values from two Walkers
// that run simultaneously, and returns true
// if t1 and t2 have the same contents.
func Compare(t1, t2 *Tree) bool {
c1, c2 := Walker(t1), Walker(t2)
for <-c1 == <-c2 {
if closed(c1) || closed(c1) {
return closed(c1) == closed(c2)
}
}
return false
}
// New returns a new, random binary tree
// holding the values 1k, 2k, ..., nk.
func New(n, k int) *Tree {
var t *Tree
for _, v := range rand.Perm(n) {
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)
return t
}
t.Right = insert(t.Right, v)
return t
}
func main() {
t1 := New(1, 100)
fmt.Println(Compare(t1, New(1, 100)), "Same Contents")
fmt.Println(Compare(t1, New(1, 99)), "Differing Sizes")
fmt.Println(Compare(t1, New(2, 100)), "Differing Values")
fmt.Println(Compare(t1, New(2, 101)), "Dissimilar")
}
希望本文所述对大家的Go语言程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 群星《爱情101情歌101延续篇 牵动心灵的情歌》6CD[WAV+CUE][4.2G]
- 【原神】璃月特产“人间美味”绝云椒椒的收集(58)
- 无相之草BOSS怎么打?无相草打法攻略
- 须弥沙漠地灵龛在哪?地灵龛位置详细介绍
- 群星.2024-生活在别处的我电视原声带【环球】【FLAC分轨】
- 陈雷.1996-最佳男主角【金圆唱片】【WAV+CUE】
- 苏妙玲.2019-WAN【天娱传媒】【FLAC分轨】
- 完美的人 A Man In Full
- 我们的生物世界 Our Living World
- 雷普利 Ripley
- 燕云十六声卷二烈言所有宝箱位置一览
- 崩坏星穹铁道神秘人交给你的线索位置大全
- 少年西游记2众生轮回活动攻略 2个玩法解析
- 出发吧麦芬古遗迹上的幽影试炼怎么过 古遗迹上的幽影阵容打法攻略
- 出发吧麦芬三宝齐聚黄金船试炼怎么过 三宝齐聚黄金船阵容打法攻略