Go语言实现的树形结构数据比较算法实例
本文实例讲述了Go语言实现的树形结构数据比较算法。分享给大家供大家参考。具体实现方法如下：
//Twobinarytreesmaybeofdifferentshapes, //buthavethesamecontents.Forexample: // // 4 6 // 2 6 4 7 // 1357 2 5 // 13 // //Go'sconcurrencyprimitivesmakeiteasyto //traverseandcomparethecontentsoftwotrees //inparallel.
packagemain import( "fmt" "rand" )
//ATreeisabinarytreewithintegervalues. typeTreestruct{ Left *Tree Valueint Right*Tree }
//Walktraversesatreedepth-first, //sendingeachValueonachannel. funcWalk(t*Tree,chchanint){ ift==nil{ return } Walk(t.Left,ch) ch<-t.Value Walk(t.Right,ch) }
//WalkerlaunchesWalkinanewgoroutine, //andreturnsaread-onlychannelofvalues. funcWalker(t*Tree)<-chanint{ ch:=make(chanint) gofunc(){ Walk(t,ch) close(ch) }() returnch }
//ComparereadsvaluesfromtwoWalkers //thatrunsimultaneously,andreturnstrue //ift1andt2havethesamecontents. funcCompare(t1,t2*Tree)bool{ c1,c2:=Walker(t1),Walker(t2) for<-c1==<-c2{ ifclosed(c1)||closed(c1){ returnclosed(c1)==closed(c2) } } returnfalse }
//Newreturnsanew,randombinarytree //holdingthevalues1k,2k,...,nk. funcNew(n,kint)*Tree{ vart*Tree for_,v:=rangerand.Perm(n){ t=insert(t,(1+v)*k) } returnt }
funcinsert(t*Tree,vint)*Tree{ ift==nil{ return&Tree{nil,v,nil} } ifv<t.Value{ t.Left=insert(t.Left,v) returnt } t.Right=insert(t.Right,v) returnt }
funcmain(){ t1:=New(1,100) fmt.Println(Compare(t1,New(1,100)),"SameContents") fmt.Println(Compare(t1,New(1,99)),"DifferingSizes") fmt.Println(Compare(t1,New(2,100)),"DifferingValues") fmt.Println(Compare(t1,New(2,101)),"Dissimilar") }