go - 为什么我的 Go 指针接收器不会导致更新？

Question

我需要一些关于 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 的局部变量 node 也将为 nil
• 因此将跳过 for 循环。
• node = NewNode(key) 将具有与 t.root = 相同的效果 新节点(键)

我的 Insert2 方法哪里出错了？有什么方法可以对其进行调整吗？

Answer 1

您似乎混淆了指针的用法。

当您执行 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) 做了你最初打算做的事情；您正在将新创建的项目分配给根指针、左指针或右指针。