Go语言实现的树形结构数据比较算法实例
本文实例讲述了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语言程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：notice#yiidian.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
