在最小堆二叉树中使用递归搜索和返回节点

Question

所以我试图通过索引检索最小堆树中的节点。调用它的方式是我会启动一个空的 MinHeapNode 结构并通过 &node 传递它的值，这样在递归函数调用之间，如果找到匹配项，它就会 return。然而，即使给出找到的结果，新分配的空节点似乎也会被另一个具有该节点空版本的递归调用覆盖。我仍然习惯了指针和地址的想法，所以我相信传递值地址可以解决这个问题，因为它会在调用之间的相同地址调用相同的值。但显然这是不正确的。

type MinHeapNode struct {
    Parent *MinHeapNode
    Left   *MinHeapNode
    Right  *MinHeapNode
    Value  int
    Index  int
}

func (MHN *MinHeapNode) Insert(value int) {

    if !MHN.hasLeftChild() {
        MHN.Left = &MinHeapNode{Parent: MHN, Value: value}
        return
    }

    if !MHN.hasRightChild() {
        MHN.Right = &MinHeapNode{Parent: MHN, Value: value}
        return
    }

    if MHN.hasLeftChild(){
        MHN.Left.Insert(value)
        return
    }

    if MHN.hasRightChild(){
        MHN.Right.Insert(value)
        return
    }
}
func (MHN *MinHeapNode) setIndex(count *int){

    index := *count
    *count = *count +1
    MHN.Index = index

    if MHN.hasLeftChild(){
        MHN.Left.setIndex(count)
    }
    
    if MHN.hasRightChild(){
        MHN.Right.setIndex(count)
    }
    
}


func (MHN *MinHeapNode) getIndex(index int, node *MinHeapNode){
    if MHN == nil{
        return
    }

    if MHN.Index == index{
        node = MHN
        return
    }
        MHN.Left.getIndex(index, node)
        MHN.Right.getIndex(index,node)
    }
}

type MinHeapTree struct {
    Root MinHeapNode
    Size int
}

func (MHT *MinHeapTree) getIndex(index int)(*MinHeapNode, error){
    if MHT.Size < index +1 {
        err := fmt.Errorf("index exceeds tree size")
        return nil, err
    } 
    var node MinHeapNode
    MHT.Root.getIndex(index, &node)
    return &node, nil

}

Answer 1

您面临的问题似乎与 getIndex 中的语句 node = MHN 有关（但由于您的代码不完整，我无法确认这是否是唯一的问题）。

node = MHN 将更新 node 的值（一个参数，所以按值传递，its scope 是函数体）。这对 node 在函数开始时指向的 MinHeapNode 的值没有影响。要更正此问题，请使用 *node = *MHN.

这可以用一个简单的程序来演示(playground)

type MinHeapNode struct {
    Test string
}

func getIndexBad(node *MinHeapNode) {
    newNode := MinHeapNode{Test: "Blah"}
    node = &newNode
}

func getIndexGood(node *MinHeapNode) {
    newNode := MinHeapNode{Test: "Blah"}
    *node = newNode
}
func main() {
    n := MinHeapNode{}
    fmt.Println(n)
    getIndexBad(&n)
    fmt.Println(n)
    getIndexGood(&n)
    fmt.Println(n)
}

输出表明“坏”函数没有更新传入的 node:

{}
{}
{Blah}

在最小堆二叉树中使用递归搜索和返回节点

Searching and Returning a node using recursion in minheap binary tree

recursion

pass-by-reference

go

heapsort