我想请一些关于 Go 指针接收器如何工作的帮助。
我在下面有一个包含的二叉搜索树示例,希望能帮助我解释。
package main
import "fmt"
type Node struct {
key int
left, right *Node
}
func NewNode(key int) *Node {
return &Node{key, nil, nil}
}
type BST struct {
root *Node
}
func NewBinarySearchTree() *BST {
return &BST{nil}
}
func (t *BST) Insert(key int) {
if t.root == nil {
t.root = NewNode(key)
return
}
var node = t.root
for {
if key < node.key {
if node.left == nil {
node.left = NewNode(key)
return
} else {
node = node.left
}
} else {
if node.right == nil {
node.right = NewNode(key)
return
} else {
node = node.right
}
}
}
}
func inorder(node *Node) {
if node == nil {
return
}
inorder(node.left)
fmt.Print(node.key, " ")
inorder(node.right)
}
func main() {
tree := NewBinarySearchTree()
tree.Insert(3)
tree.Insert(1)
tree.Insert(2)
tree.Insert(4)
inorder(tree.root) // 1 2 3 4
}
但是,在我写完这篇文章之后,我想我可以简化我的插入函数,如下所示:
func (t *BST) Insert2(key int) {
var node *Node
node = t.root
for node != nil {
if key < node.key {
node = node.left
} else {
node = node.right
}
}
node = NewNode(key)
}
但是,这样做会使树永远不会更新。我的想法是...
- 在第一次插入时,根节点将为 NIL。
- 所以引用 t.root 的局部变量节点也将为 nil
- 因此,将跳过 for 循环。
-
node = NewNode(key)
将具有与t.root = NewNode(key)
相同的效果
我的 Insert2 方法哪里出错了?有没有办法调整它?
您似乎混淆了指针的使用。
当你做node = t.root
时,你只是node
指向t.root
所指向的任何东西。
稍后,当您执行node = NewNode(key)
时,您将node
指向新创建的项目,这不是您想要的;您希望t.root
指向该新项目。
由于您打算修改类型为 *Node
的变量(root
、left
和 right
),我们需要一个指向它们的指针,因此一个 **Node
类型的变量,具有另一个间接级别。
你可以从node
指向t.root
的地址开始,node := &t.root
,然后继续循环。
您可以尝试如下操作:
func (t *BST) Insert3(key int) {
node := &t.root
for *node != nil {
if key < (*node).key {
node = &(*node).left
} else {
node = &(*node).right
}
}
*node = NewNode(key)
}
请注意,在检查循环上的地址以及密钥时,我们使用间接寻址运算符*
来访问引用的数据。
在函数结束时,*node = NewNode(key)
执行您最初打算执行的操作;您将新创建的项分配给根、左或右指针。
node = NewNode(key)
这条线不会改变树。该行更改局部变量node
;在此行之后,node
指向不同的 Node,但它过去指向的对象不受影响。要插入到树中,您必须分配给 t.root
、 node.left
或 node.right
。