# 【GoLang笔记】A Tour of Go - Exercise: Equivalent Binary Trees

slvher · · 1604 次点击 · · 开始浏览

Exercise: Equivalent Binary Trees
1. Implement the Walk function.
2. Test the Walk function.

The function tree.New(k) constructs a randomly-structured binary tree holding the values k,2k, 3k, ..., 10k.

Create a new channel ch and kick off the walker:

go Walk(tree.New(1), ch)

Then read and print 10 values from the channel. It should be the numbers 1, 2, 3, ..., 10.

3. Implement the Same function using Walk to determine whether t1 and t2 store the same values.

4. Test the Same function.

Same(tree.New(1), tree.New(1)) should return true, and Same(tree.New(1), tree.New(2))should return false.

```package main

import "fmt"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
//fmt.Println("tree=", t)
left := t.Left
right := t.Right
if (left == nil) && (right == nil) {
//fmt.Println("child=", t.Value)
ch <- t.Value
return
}

if left != nil {
Walk(left, ch)
}

if (left != nil) || (right != nil) {
//fmt.Println("parent=", t.Value)
ch <- t.Value
}

if right != nil {
Walk(right, ch)
}
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)

depth := 10
for i := 0; i < depth; i++ {
x1 := <- ch1
x2 := <- ch2
if x1 != x2 {
return false
}
}

return true
}

func main() {
/*
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(tree.New(1), ch1)
go Walk(tree.New(2), ch2)

for i := 0; i < 10; i++ {
fmt.Println(<-ch1)
}
for i := 0; i < 10; i++ {
fmt.Println(<-ch2)
}
*/
fmt.Println(Same(tree.New(1), tree.New(2)))
}
```

===================== EOF ===================

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

Exercise: Equivalent Binary Trees
1. Implement the Walk function.
2. Test the Walk function.

The function tree.New(k) constructs a randomly-structured binary tree holding the values k,2k, 3k, ..., 10k.

Create a new channel ch and kick off the walker:

go Walk(tree.New(1), ch)

Then read and print 10 values from the channel. It should be the numbers 1, 2, 3, ..., 10.

3. Implement the Same function using Walk to determine whether t1 and t2 store the same values.

4. Test the Same function.

Same(tree.New(1), tree.New(1)) should return true, and Same(tree.New(1), tree.New(2))should return false.

```package main

import "fmt"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
//fmt.Println("tree=", t)
left := t.Left
right := t.Right
if (left == nil) && (right == nil) {
//fmt.Println("child=", t.Value)
ch <- t.Value
return
}

if left != nil {
Walk(left, ch)
}

if (left != nil) || (right != nil) {
//fmt.Println("parent=", t.Value)
ch <- t.Value
}

if right != nil {
Walk(right, ch)
}
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(t1, ch1)
go Walk(t2, ch2)

depth := 10
for i := 0; i < depth; i++ {
x1 := <- ch1
x2 := <- ch2
if x1 != x2 {
return false
}
}

return true
}

func main() {
/*
ch1 := make(chan int)
ch2 := make(chan int)
go Walk(tree.New(1), ch1)
go Walk(tree.New(2), ch2)

for i := 0; i < 10; i++ {
fmt.Println(<-ch1)
}
for i := 0; i < 10; i++ {
fmt.Println(<-ch2)
}
*/
fmt.Println(Same(tree.New(1), tree.New(2)))
}
```

===================== EOF ===================