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)文章
我們?cè)谑褂肎olang時(shí)，不可避免會(huì)遇到異常情況的處理，與Java、Python等語(yǔ)言不同的是，Go中并沒(méi)有try...catch...這樣的語(yǔ)句塊，這個(gè)時(shí)候我們?nèi)绾尾拍芨玫奶幚懋惓Ｄ?？本文?lái)教你正確方法2023-03-03
用golang實(shí)現(xiàn)一個(gè)定時(shí)器任務(wù)隊(duì)列實(shí)例
golang中提供了2種定時(shí)器timer和ticker，分別是一次性定時(shí)器和重復(fù)任務(wù)定時(shí)器。這篇文章主要介紹了用golang實(shí)現(xiàn)一個(gè)定時(shí)器任務(wù)隊(duì)列實(shí)例，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2018-05-05
Golang 實(shí)現(xiàn) Redis系列(六)如何實(shí)現(xiàn) pipeline 模式的 redis 客戶端
pipeline 模式的 redis 客戶端需要有兩個(gè)后臺(tái)協(xié)程負(fù)責(zé) tcp 通信，調(diào)用方通過(guò) channel 向后臺(tái)協(xié)程發(fā)送指令，并阻塞等待直到收到響應(yīng)，本文是使用 golang 實(shí)現(xiàn) redis 系列的第六篇， 將介紹如何實(shí)現(xiàn)一個(gè) Pipeline 模式的 Redis 客戶端。2021-07-07
這篇文章主要介紹了golang 獲取文件夾下面的文件列表方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-05-05
gorm FirstOrCreate和受影響的行數(shù)實(shí)例
這篇文章主要介紹了gorm FirstOrCreate和受影響的行數(shù)實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12
這篇文章主要介紹了Go語(yǔ)言掃描目錄并獲取相關(guān)信息的方法,實(shí)例分析了Go語(yǔ)言操作目錄及文件的技巧,需要的朋友可以參考下2015-03-03
Golang 支持交叉編譯，在一個(gè)平臺(tái)上生成另一個(gè)平臺(tái)的可執(zhí)行程序,只需要按照我下面的這個(gè)環(huán)境變量表設(shè)置對(duì)應(yīng)的環(huán)境變量就可以了，下面文章將對(duì)該內(nèi)容做詳細(xì)介紹，感興趣的小伙伴可以參考一下2021-10-10
這篇文章主要介紹了golang獲得一個(gè)變量類型的實(shí)現(xiàn)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-05-05
Golang中ringbuffer的實(shí)現(xiàn)與應(yīng)用場(chǎng)景詳解
ringbuffer因?yàn)樗軓?fù)用緩沖空間，通常用于網(wǎng)絡(luò)通信連接的讀寫，雖然市面上已經(jīng)有了go寫的諸多版本的ringbuffer組件，但還是自己造一個(gè)吧2023-06-06
Go語(yǔ)言異常處理(Panic和recovering)用法詳解
異常處理是程序健壯性的關(guān)鍵，往往開(kāi)發(fā)人員的開(kāi)發(fā)經(jīng)驗(yàn)的多少?gòu)漠惓２糠痔幚砩暇湍艿玫襟w現(xiàn)。Go語(yǔ)言中沒(méi)有Try?Catch?Exception機(jī)制，但是提供了panic-and-recover機(jī)制，本文就來(lái)詳細(xì)講講他們的用法2022-07-07