How do you perform a deep copy of a ternary tree in Go?

huangapple
go评论113阅读模式
英文:

How do you perform a deep copy of a ternary tree in Go?

问题

我正在尝试对以下结构体执行深拷贝：

// 三叉树
type Tree struct {
Left *Tree
Mid *Tree
Right *Tree
Value interface{}
Parent *Tree
Orientation string
IsTerminal bool
Type string
}

以下是我尝试的代码。看起来我在根节点创建了一个新的树，但它的子节点仍然指向相同的内存地址。

func (tree *Tree) CopyTree() *Tree {
if (tree == nil) {
return nil
} else {
copiedTree := &Tree {
tree.Left.CopyTree(),
tree.Mid.CopyTree(),
tree.Right.CopyTree(),
tree.Value,
tree.Parent.CopyTree(),
tree.Orientation,
tree.IsTerminal,
tree.Type}
return copiedTree
}
}

Go语言中是否有任何有用的构造来辅助深拷贝一个结构体？如果没有，我该如何自己执行这个深拷贝？请注意，"deepcopy"包在Go 1发布时使用了一些已被弃用的函数，因此不再可用。

英文:

I'm attempting to perform a deep copy of the following struct:

  1. // Ternary Tree
  2. type Tree struct {
  3.     Left  *Tree
  4.     Mid *Tree
  5.     Right *Tree
  6.     Value interface{}
  7.     Parent *Tree
  8.     Orientation string
  9.     IsTerminal bool
  10.     Type string
  11. }

The following is my sorry attempt. It looks like I'm creating a new tree at the root but it's children are still pointing to the same address in memory.

  1. func (tree *Tree) CopyTree() *Tree {
  2.     if (tree == nil) {
  3.         return nil
  4.     } else {
  5.         copiedTree := &Tree {
  6.             tree.Left.CopyTree(),
  7.             tree.Mid.CopyTree(),
  8.             tree.Right.CopyTree(),
  9.             tree.Value,
  10.             tree.Parent.CopyTree(),
  11.             tree.Orientation,
  12.             tree.IsTerminal,
  13.             tree.Type}
  14.         return copiedTree
  15.     }
  16. }

Are there any useful constructs in go that assist with deep copying a struct? If not, how would I perform this deep copy myself? Note, the "deepcopy" package no longer works as it uses a few functions that were deprecated with the release of Go 1

答案1

得分: 10

我离成功很近了。我应该将copiedTree赋值给parent属性。

  1. func (tree *Tree) CopyTree() *Tree {
  2.     if (tree == nil) {
  3.         return nil
  4.     } else {
  5.         copiedTree := &Tree {
  6.             tree.Left.CopyTree(),
  7.             tree.Mid.CopyTree(),
  8.             tree.Right.CopyTree(),
  9.             tree.Value,
  10.             nil,
  11.             tree.Orientation,
  12.             tree.IsTerminal,
  13.             tree.Type,
  14.         }
  15.     
  16.         if copiedTree.Left != nil {
  17.             copiedTree.Left.Parent = copiedTree
  18.         }
  19.         if copiedTree.Right != nil {
  20.             copiedTree.Right.Parent = copiedTree
  21.         }
  22.         if copiedTree.Mid != nil {
  23.             copiedTree.Mid.Parent = copiedTree
  24.         }
  25.         return copiedTree
  26.     }
  27. }
英文:

I was close. I should have assigned the copiedTree to the parent property.

  1. func (tree *Tree) CopyTree() *Tree {
  2.     if (tree == nil) {
  3.         return nil
  4.     } else {
  5.         copiedTree := &Tree {
  6.             tree.Left.CopyTree(),
  7.             tree.Mid.CopyTree(),
  8.             tree.Right.CopyTree(),
  9.             tree.Value,
  10.             nil,
  11.             tree.Orientation,
  12.             tree.IsTerminal,
  13.             tree.Type,
  14.         }
  15.     
  16.         if copiedTree.Left != nil {
  17.             copiedTree.Left.Parent = copiedTree
  18.         }
  19.         if copiedTree.Right != nil {
  20.             copiedTree.Right.Parent = copiedTree
  21.         }
  22.         if copiedTree.Mid != nil {
  23.             copiedTree.Mid.Parent = copiedTree
  24.         }
  25.         return copiedTree
  26.     }
  27. }

答案2

得分: 0

你可以通过encoding/gob来进行往返转换：

  1. package main
  3. import (
  4.    "bytes"
  5.    "encoding/gob"
  6. )
  8. func copyStruct(in, out interface{}) {
  9.    buf := new(bytes.Buffer)
  10.    gob.NewEncoder(buf).Encode(in)
  11.    gob.NewDecoder(buf).Decode(out)
  12. }
  14. func main() {
  15.    type date struct { Month, Day int }
  16.    a := date{12, 31}
  17.    var b date
  18.    copyStruct(a, &b)
  19. }

https://golang.org/pkg/encoding/gob

英文:

You can roundtrip it through encoding/gob:

  1. package main
  3. import (
  4.    "bytes"
  5.    "encoding/gob"
  6. )
  8. func copyStruct(in, out interface{}) {
  9.    buf := new(bytes.Buffer)
  10.    gob.NewEncoder(buf).Encode(in)
  11.    gob.NewDecoder(buf).Decode(out)
  12. }
  14. func main() {
  15.    type date struct { Month, Day int }
  16.    a := date{12, 31}
  17.    var b date
  18.    copyStruct(a, &b)
  19. }

https://golang.org/pkg/encoding/gob

答案3

得分: -1

json.Marshal和json.Unmarshal怎么样？如果性能很重要，我更倾向于使用protobuf。

英文:

How about json.Marshal and json.Unmarshal. If performance is critical, I perfer to use protobuf.

huangapple
  • 本文由 发表于 2014年10月28日 07:24:38
  • 转载请务必保留本文链接：https://go.coder-hub.com/26598524.html
  • deep-copy
  • go
  • ternary-tree
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定