为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

Go
狐的传说 2022-11-23 19:16:57

所以我试图通过索引检索最小堆树中的节点。调用它的方式是我会启动一个空的 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


}


查看完整描述

1 回答

?
哆啦的时光机

TA贡献1513条经验 获得超6个赞

您面临的问题似乎与中的声明node = MHN有关getIndex(但由于您的代码不完整,我无法确认这是否是唯一的问题)。


node = MHN将更新node(一个参数,所以按值传递,它的作用域是函数体)的值。MinHeapNode这对函数node开头指向的值没有影响。纠正这个用法*node = *MHN。


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


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}


查看完整回答
反对 回复 2022-11-23

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信