欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Go语言实现的树形结构数据比较算法实例

程序员文章站 2022-06-24 11:59:16
本文实例讲述了go语言实现的树形结构数据比较算法。分享给大家供大家参考。具体实现方法如下: 复制代码 代码如下: // two binary trees may be...

本文实例讲述了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语言程序设计有所帮助。