去旅游锻炼#7:漫步树
去旅游锻炼#7:漫步树
提问于 2012-08-27 01:28:52
我完成了进行树比较的go巡回练习(#69)，并且能够有效地比较两棵树。
这里是代码
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
c := make(chan int)
c2 := make(chan int)
go Walk(t1, c)
go Walk(t2, c2)
for i := 0; i < 10; i++ {
if <-c != <-c2 {
return false
}
}
return true
}
func main() {
fmt.Println(Same(tree.New(1), tree.New(1)))
}让我困惑的部分是，如果我切换遍历函数中命令的顺序，
ch <- t.Value
Walk(t.Right,ch)
Walk(t.Left,ch)这种比较已不再有效。我试着打印两次Walk(tree.New(1)，c)的结果，奇怪的是第一次打印的调用
10,5,7,9...而第二次调用的步行(tree.New(1)，c)打印
7,9,10,8...为什么在切换遍历命令的顺序时，调用相同的函数两次会产生两个不同的输出？
回答 2
Stack Overflow用户
回答已采纳
发布于 2012-08-27 02:33:11
首先，您需要了解树的属性。树被设置为左边的数字总是小于当前节点的值。右边的数字总是更多。
因此，如果您想要找到最小的数字，您所需要做的就是在每个节点上“左转”。如果你去找最低数字的父级，你得到的是第二低的。第二最低的正确子女可能是也可能不是第三最低的。然而，如果你在每一次机会中从第二低的右子处左转，你就会落在第三低的位置。这是在遍历每个节点之前完成的。
当您Walk()树时，实际上是对数字进行排序。
Walk(t.Left,ch)
ch <- t.Value
Walk(t.Right,ch)左边，现在，右边。最低，第二最低，第三最低。
ch <- t.Value
Walk(t.Right,ch)
Walk(t.Left,ch)这是目前的，右，左。第二最低，第三最低，最低。这种排序的问题是，它们所出的顺序取决于树的顺序。在第一种情况下，重要的是树中的元素，而不是顺序。
Walk()函数真正实现的是树排序算法的一部分。请参阅：排序
Stack Overflow用户
发布于 2012-08-27 16:24:49
看看树的源代码：
// 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
}它使用Perm函数：
Perm作为n个ints的切片返回整数[0，n]的伪随机排列。
您看到的是一个特性:由New创建的每一棵树都是随机的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12135333
复制相关文章
相似问题
腾讯云开发者
