Поиск и возврат узла с использованием рекурсии в двоичном дереве minheap
Итак, я пытаюсь получить узел в дереве minheap по индексу. Способ, которым он будет вызываться, заключается в том, что я инициирую пустую структуру 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
Проблема, с которой вы столкнулись, связана с утверждением 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}