遍历树,试图理解代码。

huangapple go评论82阅读模式
英文:

Go tree traversal, trying to understand the code

问题

我正在查看Rosettacode.org上关于树遍历的页面。我正在查看Go语言的实现,我对Go相当新,所以我希望你能帮助我。

在文件的开头,创建了一个结构体。这很好,到目前为止都很有意义。但是我不明白的是这个部分:

type node struct {
    value       int
    left, right *node
}

left, right *node 这部分。我理解 left、right 变量的类型是指向 node 的指针。但是我不明白为什么首先我不知道你可以在实际的结构体中包含你正在创建的类型,即在这种情况下是 node。然后我真的不明白为什么代码不直接写成 left, right node

func (n *node) iterPreorder(visit func(int)) {
    if n == nil {
        return
    }
    visit(n.value)
    n.left.iterPreorder(visit)
    n.right.iterPreorder(visit)
}

接下来我不明白的是,visit 变量如何是 func(int) 类型的。然后我也不明白为什么你可以在函数 iterPreorder 中使用 iterPreorder

最后我想问一下,这段代码是做什么的?

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

谢谢,这是链接到Rosettacode.org上完整代码的链接。

英文:

I'm looking at this page on Rosettacode.org about tree traversal. I'm looking at the Go implementation, I'm fairly new to Go which is why I'd like your help.

Right at the beginning of the file, a struct is created. That's ok it makes sense so far. But the thing I don't understand is this:

type node struct {
    value       int
    left, right *node
}

The left, right *node part. I understand that the left, right variables are of type pointer to node. But I don't understand why, first-off I didn't know you could include the type you are creating, in this case node in the actual struct itself. And then I don't really understand why the code doesn't just say left, right node.

func (n *node) iterPreorder(visit func(int)) {
    if n == nil {
        return
    }
    visit(n.value)
    n.left.iterPreorder(visit)
    n.right.iterPreorder(visit)
}

The next thing I don't get is, how the visit variable can be of type func(int). Then I also don't get how you can use iterPreorder within the function iterPreorder.

And finally I'd just like to ask, what does this code do?

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

Thanks, here's a link to the full code over on Rosettacode.org.

答案1

得分: 6

让我们一步一步来。

  1. 它使用指针是因为左侧和/或右侧可以为nil(未设置),使用值无法实现这一点。此外,如果使用left, right node,由于该值将始终被设置,你将拥有无限数量的节点。

  2. visit func(int) 允许你传递一个类型为 func(int) 的函数,类似于其他语言中的回调函数。

  3. n.left.iterPreorder / n.right.iterPreorder,实际上是在子节点上调用 iterPreorder,而不是从调用它的相同节点上调用。

  4. 代码简单地创建了一棵树并分配了它的节点。

为了更好地可视化它:

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

与以下代码相同:

tree = &node{value: 1}
tree.left = &node{value:2}
tree.left.left = &node{value: 4}
tree.left.left.left = &node{value: 7}
tree.left.right = &node{value: 5}

tree.right = &node{value:3}
tree.right.left = &node{value: 6}
tree.right.left.left = &node{value: 8}
tree.right.left.right = &node{value: 9}

额外内容

  • 使用& 返回一个指针,例如 n := &node{}n 是一个指向节点的指针。

请查看关于Go指针的这篇优秀文章

此外,Effective Go 是必读的,还可以尝试完成 tour

英文:

Let's take it step by step.

  1. It uses pointers because left and/or right can be nil (not set at all), you can't have that with a value. Also if they used left, right node you would have an infiniate number of nodes since that value will always be set.

  2. visit func(int) allows you to pass a function of the type func(int), like callbacks in other languages.

  3. n.left.iterPreorder / n.right.iterPreorder, you're actually calling iterPreorder on a child node, not the same node it got called from.

  4. The code simply creates a tree and assigns it's nodes.

To visualize it better:

tree := &node{1,
    &node{2,
        &node{4,
            &node{7, nil, nil},
            nil},
        &node{5, nil, nil}},
    &node{3,
        &node{6,
            &node{8, nil, nil},
            &node{9, nil, nil}},
        nil}}

Is the same as:

tree = &node{value: 1}
tree.left = &node{value:2}
tree.left.left = &node{value: 4}
tree.left.left.left = &node{value: 7}
tree.left.right = &node{value: 5}

tree.right = &node{value:3}
tree.right.left = &node{value: 6}
tree.right.left.left = &node{value: 8}
tree.right.left.right = &node{value: 9}

bonus:

  • Using & returns a pointer, for example n := &node{}, n is a pointer to a node.

Check this excellent article about Go pointers.

Also Effective Go is a must a read, and try going through the tour

huangapple
  • 本文由 发表于 2014年8月18日 01:33:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/25351804.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定