2

我完成了树比较的 go tour 练习 (#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)))
}

让我感到困惑的部分是，如果我将 walk 函数中的命令顺序切换为

    ch <- t.Value
    Walk(t.Right,ch)
    Walk(t.Left,ch)

比较不再有效。我尝试两次打印出 Walk(tree.New(1),c) 的结果，奇怪的是第一次调用打印

    10,5,7,9...

而第二次调用 Walk(tree.New(1),c) 打印

    7,9,10,8...

为什么在切换walk命令的顺序时两次调用相同的函数会导致两个不同的输出？

4

2 回答 2

4

首先，您需要了解树的属性。树的设置使得左边的数字总是小于当前节点的值。右边的数字总是更多。

因此，如果您想找到最小的数字，您需要做的就是在每个节点上“向左”。如果你去最低数字的父母，你会得到第二低的。第二低的右孩子可能是也可能不是第三低的。然而，如果你每次都从第二低的右孩子那里取一个左，你最终会排在第三低。这样做直到遍历完每个节点。

当您Walk()创建树时，您实际上是在对数字进行排序。

Walk(t.Left,ch)
ch <- t.Value
Walk(t.Right,ch)

左，当前，右。最低，第二低，第三低。

ch <- t.Value
Walk(t.Right,ch)
Walk(t.Left,ch)

这是当前的，右，左。第二低，第三低，最低。这种排序的问题是它们出现的顺序取决于树的顺序。在第一个中，重要的是树中的元素，而不是顺序。

该Walk()函数真正实现的是树排序算法的一部分。见：http ://en.wikipedia.org/wiki/Tree_sort

于 2012-08-27T02:33:11.327 回答
2

查看Tree 的源代码：

// 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 个整数的切片返回整数 [0,n) 的伪随机排列。

您看到的是一个特征：由其创建的每棵树New都是随机的。

于 2012-08-27T16:24:49.210 回答