2

木の比較のためのゴーツアー演習 (#69) を完了し、2 本の木を効果的に比較することができました。

ここにコードがあります

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) の結果を 2 回印刷しようとしましたが、奇妙なことに最初の呼び出しが印刷されました

    10,5,7,9...

Walk(tree.New(1),c) の 2 回目の呼び出しが出力されている間

    7,9,10,8...

walk コマンドの順序を切り替えるときに、同じ関数を 2 回呼び出すと、2 つの異なる出力が生じるのはなぜですか?

4

2 に答える 2

4

まず、ツリーのプロパティを理解する必要があります。ツリーは、左側の数値が常に現在のノードの値よりも小さくなるように設定されています。右側の数字は常に多くなります。

したがって、最小の数を見つけたい場合は、各ノードで「左」に移動するだけです。最小数の親に移動すると、2 番目に小さい数になります。2 番目に下の子の右の子は、3 番目に下にある場合とそうでない場合があります。ただし、下から2番目の子の右の子から、たまたま左を取ってしまうと、下から3番目の子になってしまいます。これは、すべてのノードがトラバースされるまで行われます。

Walk()ツリーを作成するとき、実際には数字を並べ替えています。

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

それは左、現在、右に行きます。最低、2 番目に低い、3 番目に低い。

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

これは現在、右、左になります。2 番目に低い、3 番目に低い、最も低い。この順序の問題は、それらが出てくる順序がツリーの順序に依存することです。最初のものでは、順序ではなく、ツリー内の要素が重要です。

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 は、整数 [0,n) の疑似乱数順列を n 個の int のスライスとして返します。

表示されるのは機能です。作成された各ツリーNewはランダムです。

于 2012-08-27T16:24:49.210 に答える