英文:
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
让我们一步一步来。
-
它使用指针是因为左侧和/或右侧可以为nil(未设置),使用值无法实现这一点。此外,如果使用
left, right node
,由于该值将始终被设置,你将拥有无限数量的节点。 -
visit func(int)
允许你传递一个类型为func(int)
的函数,类似于其他语言中的回调函数。 -
n.left.iterPreorder
/n.right.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}}
与以下代码相同:
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.
-
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. -
visit func(int)
allows you to pass a function of the typefunc(int)
, like callbacks in other languages. -
n.left.iterPreorder
/n.right.iterPreorder
, you're actually callingiterPreorder
on a child node, not the same node it got called from. -
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 examplen := &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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论