Go語(yǔ)言實(shí)現(xiàn)的樹(shù)形結(jié)構(gòu)數(shù)據(jù)比較算法實(shí)例
本文實(shí)例講述了Go語(yǔ)言實(shí)現(xiàn)的樹(shù)形結(jié)構(gòu)數(shù)據(jù)比較算法。分享給大家供大家參考。具體實(shí)現(xiàn)方法如下:
// 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")
}
希望本文所述對(duì)大家的Go語(yǔ)言程序設(shè)計(jì)有所幫助。
相關(guān)文章
golang如何通過(guò)viper讀取config.yaml文件
這篇文章主要介紹了golang通過(guò)viper讀取config.yaml文件,圍繞golang讀取config.yaml文件的相關(guān)資料展開(kāi)詳細(xì)內(nèi)容,需要的小伙伴可以參考一下2022-03-03Go處理JSON數(shù)據(jù)的實(shí)現(xiàn)
本文主要介紹了Go處理JSON數(shù)據(jù)的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02一文詳解Go語(yǔ)言中的有限狀態(tài)機(jī)FSM
有限狀態(tài)機(jī)(Finite?State?Machine,F(xiàn)SM)是一種數(shù)學(xué)模型,用于描述系統(tǒng)在不同狀態(tài)下的行為和轉(zhuǎn)移條件。本文主要來(lái)和大家簡(jiǎn)單講講Go語(yǔ)言中的有限狀態(tài)機(jī)FSM的使用,需要的可以參考一下2023-04-04Go語(yǔ)言中匿名嵌套和類(lèi)型嵌套的區(qū)別解析
在Go語(yǔ)言中,匿名嵌套結(jié)構(gòu)體和與類(lèi)型同名的嵌套結(jié)構(gòu)體不是完全等價(jià)的,它們有一些重要的區(qū)別,這篇文章主要介紹了Go語(yǔ)言中匿名嵌套和類(lèi)型嵌套的區(qū)別,需要的朋友可以參考下2023-09-09