實(shí)現(xiàn)兩個(gè)二叉樹(shù)的比較。二叉樹(shù)的基本類(lèi)型和函數(shù)來(lái)源于 “golang.org/x/tour/tree”粟判，為了避免網(wǎng)絡(luò)問(wèn)題影響代碼運(yùn)行，我把源碼直接加入到了代碼中峦剔。
// A Tree is a binary tree with integer values.
type Tree struct {
Left *Tree
Value int
Right *Tree
}
// New returns a new, random binary tree holding the values k, 2k, ..., 10k.
func New(k int) *Tree {
var t *Tree
for _, v := range rand.Perm(10) {
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)
} else {
t.Right = insert(t.Right, v)
}
return t
}
func (t *Tree) String() string {
if t == nil {
return "()"
}
s := ""
if t.Left != nil {
s += t.Left.String() + " "
}
s += fmt.Sprint(t.Value)
if t.Right != nil {
s += " " + t.Right.String()
}
return "(" + s + ")"
}
以上代碼實(shí)現(xiàn)了二叉樹(shù)的基本功能档礁。下面我們來(lái)實(shí)現(xiàn)二叉樹(shù)的比較。
要比較兩個(gè)二叉樹(shù)是否一致吝沫。我們建立一個(gè)函數(shù)呻澜。Same(t1, t2 *Tree) bool
為了比較二叉樹(shù)，必要把二叉樹(shù)的值放進(jìn)一個(gè)通道中惨险。共使用兩個(gè)通道來(lái)進(jìn)行比較羹幸。放入通道中的函數(shù)我們建立為 Walk(t *Tree, ch chan int) 同時(shí)再建立一個(gè)遞歸函數(shù)，用來(lái)遍歷二叉樹(shù)所有的葉子節(jié)點(diǎn) rangeTree(t *Tree, ch chan int)
//遍歷二叉樹(shù)辫愉，把當(dāng)前節(jié)點(diǎn)值傳入通道
func rangeTree(t *Tree, ch chan int) {
if t != nil{
rangeTree(t.Left, ch)
ch <- t.Value
rangeTree(t.Right, ch)
}
}
// Walk 步進(jìn) tree t 將所有的值從 tree 發(fā)送到 channel ch栅受。
func Walk(t *Tree, ch chan int){
rangeTree(t, ch)
close(ch)
}
// Same 檢測(cè)樹(shù) t1 和 t2 是否含有相同的值。
func Same(t1, t2 *Tree) bool{
//建立兩個(gè)通道
ch1 := make(chan int)
ch2 := make(chan int)
//遍歷兩個(gè)二叉樹(shù)恭朗，把值傳入各自的通道
go Walk(t1, ch1)
go Walk(t2, ch2)
//遍歷通道進(jìn)行比較屏镊，有不同的值就返回false
for i := range ch1{
if i != <- ch2{
return false
}
}
return true
}
然后在 main函數(shù)中比較兩個(gè) tree
fmt.Println(Same(New(1), New(1)))
fmt.Println(Same(New(1), New(2)))
完整代碼示例
package main
import (
"fmt"
"math/rand"
)
// A Tree is a binary tree with integer values.
type Tree struct {
Left *Tree
Value int
Right *Tree
}
// New returns a new, random binary tree holding the values k, 2k, ..., 10k.
func New(k int) *Tree {
var t *Tree
for _, v := range rand.Perm(10) {
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)
} else {
t.Right = insert(t.Right, v)
}
return t
}
func (t *Tree) String() string {
if t == nil {
return "()"
}
s := ""
if t.Left != nil {
s += t.Left.String() + " "
}
s += fmt.Sprint(t.Value)
if t.Right != nil {
s += " " + t.Right.String()
}
return "(" + s + ")"
}
// Walk 步進(jìn) tree t 將所有的值從 tree 發(fā)送到 channel ch。
func Walk(t *Tree, ch chan int){
rangeTree(t, ch)
close(ch)
}
//遍歷二叉樹(shù)痰腮，把當(dāng)前節(jié)點(diǎn)值傳入通道
func rangeTree(t *Tree, ch chan int) {
if t != nil{
rangeTree(t.Left, ch)
ch <- t.Value
rangeTree(t.Right, ch)
}
}
// Same 檢測(cè)樹(shù) t1 和 t2 是否含有相同的值而芥。
func Same(t1, t2 *Tree) bool{
//建立兩個(gè)通道
ch1 := make(chan int)
ch2 := make(chan int)
//遍歷兩個(gè)二叉樹(shù)，把值傳入各自的通道
go Walk(t1, ch1)
go Walk(t2, ch2)
//遍歷通道進(jìn)行比較膀值，有不同的值就返回false
for i := range ch1{
if i != <- ch2{
return false
}
}
return true
}
func main() {
fmt.Println("二叉樹(shù)遍歷比較")
fmt.Println("打印 New(1)的值")
//打印 New(1)的值
var ch1 = make(chan int)
go Walk(New(1), ch1)
for v := range ch1{
fmt.Println(v)
}
fmt.Println("打印 New(2)的值")
//打印 New(2)的值
var ch2 = make(chan int)
go Walk(New(2), ch2)
for v := range ch2{
fmt.Println(v)
}
//比較兩個(gè)tree的值是否相等
fmt.Println(Same(New(1), New(1)))
fmt.Println(Same(New(1), New(2)))
}
運(yùn)行結(jié)果
二叉樹(shù)遍歷比較
打印 New(1)的值
1
2
3
4
5
6
7
8
9
10
打印 New(2)的值
2
4
6
8
10
12
14
16
18
20
true
false
