golang树遍历顺序

Question

刚开始尝试golang，一直卡在教程中尝试搞清楚树遍历练习

我无法弄清楚树遍历的不同顺序如何影响等效树的golang教程结果(https://tour.golang.org/concurrency/8)

具体...这是怎么...

func Walk(t *tree.Tree, ch chan int){
    ch<-t.Value
    if t.Left != nil{
        Walk(t.Left, ch)
    }
    if t.Right != nil{
        Walk(t.Right, ch)
    }
}

与此不同...

func Walk(t *tree.Tree, ch chan int){

    if t.Left != nil{
        Walk(t.Left, ch)
    }
    ch<-t.Value
    if t.Right != nil{
        Walk(t.Right, ch)
    }
}

我原以为两者都会通过以下函数提供相同的结果:

func Same(t1, t2 *tree.Tree) bool{
    chTree1 := make(chan int)
    chTree2 := make(chan int)

    go Walk(t1, chTree1)
    go Walk(t2, chTree2)

    for i:= 0; i < 10; i++{
        a, b := <-chTree1, <-chTree2
        //fmt.Printf("a: %v, b: %v\n", a, b)

        if a != b {
            return false
        }
    }
    return true
}

Answer 1

这是因为 New 的实现方式:

func New func New(k int) *Tree 

New returns a new, random binary tree holding the values k, 2k, ..., 10k.

因此，虽然使用 tree.New(1) 创建的两棵树将具有不同的结构，但它们将具有完全相同的元素。

您的第二个 Walk 实现(如下):

func Walk(t *tree.Tree, ch chan int){

    if t.Left != nil{
        Walk(t.Left, ch)
    }
    ch<-t.Value
    if t.Right != nil{
        Walk(t.Right, ch)
    }
}

正在执行 inorder traversal树的。中序遍历总是按排序顺序返回树的元素。

因此，对 tree.New(k) 使用相同的 k 值调用此 Walk 将产生相同的列表元素，即k, 2k, ..., 10k。

这导致此版本的 Walk 始终返回 true。