使用递归在 minheap 二叉树中查找节点

珍惜时间，勤奋学习！今天给大家带来《使用递归在 minheap 二叉树中查找节点》，正文内容主要涉及到等等，如果你正在学习Golang，或者是对Golang有疑问，欢迎大家关注我！后面我会持续更新相关内容的，希望都能帮到正在学习的大家！

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

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

}

正确答案

您面临的问题似乎与 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}

本篇关于《使用递归在 minheap 二叉树中查找节点》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！