重新平衡树后如何更改接收器类型（根节点）

Question

我正在尝试在 Go 中实现二叉树，但目前我陷入了树的重新平衡。重新平衡后，根节点很可能会发生变化。由于根节点是接收器类型，我必须更改接收器类型指向的值。之前的根节点现在被用作另一个节点，这就导致这个节点现在也是根节点的情况。

func (n *treeNode) rebalance()  {  

    sorted := n.traverseTree([]*treeNode{})  //returns a sorted array of *treeNode

    newRoot := innerRebalance(sorted) //the method gives the correct result

    *n = *newRoot//now I have a cyclic reference in the tree

}

重新平衡是在 add 函数中调用的。我不想公开重新平衡方法，因为它是一个实现细节。我想在 Add 方法中调用重新平衡方法。

界面：

type Store interface {

    Add(key string, value string)

    Get(key string) string

    Remove(key string) bool

}

树节点结构：

type treeNode struct {

    bigger           *treeNode

    smaller          *treeNode

    key              string

    value            string

}

例子

重新平衡前

100（根） --> 150 --> 200

重新平衡后

100 <-- 150（根）--> 200

赋值给 *n 后

... 150 <-- 150 <-- 150 --> 200

如何更改接收器类型而不获取对其自身的循环引用？

Answer 1

你要改变的实际上是**n，所以它可以指向另一个节点。在当前的范围内你不能这样做。但是，您可以包装该节点并将该节点设置在该方法之外，并让该节点的方法返回一个根。例如，type tree struct {&nbsp; &nbsp; root *treeNode}func (t *tree) Remove(key string) bool {&nbsp; &nbsp; root,ok := t.root.Remove()&nbsp; &nbsp; t.root = root&nbsp; &nbsp; return ok}并更改*treeNode.Add为func (*treeNode) Add(string) *treeNode.