如何在golang中使用struct来创建二叉树？

Question

我想创建一个二叉树并初始化树使用golang。 而像这样的代码：

package Tree 

import "fmt" 

type TreeNode struct { 
    Left *TreeNode 
    Right *TreeNode 
    Value int 
} 


func InsertNodeToTree(tree *TreeNode, node *TreeNode)(){ 
    if tree == nil { 
     tree = node 
    } 
    if node.Value > tree.Value { 
     InsertNodeToTree(tree.Right, node) 
    } 
    if node.Value < tree.Value { 
     InsertNodeToTree(tree.Left, node) 
    } 
} 

func InitTree(values ...int) (root *TreeNode) { 
    rootNode := TreeNode{Value: values[0]} 
    for _, value := range values { 
     node := TreeNode{Value:value} 
     InsertNodeToTree(&rootNode, &node) 
    } 
    return &rootNode 
} 

func main() { 
    treeNode := InitTree(5, 4, 6, 8, 9, 7, 1, 3, 2) 
    fmt.Println(treeNode) 
} 

为什么树的左边和右边都为零？ 我传递了树节点的引用，为什么不工作？

Answer 1

在C/C++编程语言，你可以使用TreeNode *&tree。
但在golang编程语言中，不能使用*&。
tree只是指针的副本，所以不能将该值指向另一个TreeNode。
我修改了你的程序，它现在可以成功运行。
也许您需要这些条码：

package Tree 

type TreeNode struct { 
    Left *TreeNode 
    Right *TreeNode 
    Value int 
} 


var DefaultValue int = -1024 


func InsertNodeToTree(tree *TreeNode, node *TreeNode)(){ 
    if tree == nil { 
     return 
    } 
    if tree.Value == DefaultValue { 
     tree.Value = node.Value 
     return 
    } 
    if node.Value > tree.Value { 
     if tree.Right == nil { 
      tree.Right = &TreeNode{Value: DefaultValue} 
     } 
     InsertNodeToTree(tree.Right, node) 
    } 
    if node.Value < tree.Value { 
     if tree.Left == nil { 
      tree.Left = &TreeNode{Value: DefaultValue} 
     } 
     InsertNodeToTree(tree.Left, node) 
    } 
} 

func InitTree(values ...int) (root *TreeNode) { 
    rootNode := TreeNode{Value: DefaultValue, Right: nil, Left: nil} 
    for _, value := range values { 
     node := TreeNode{Value:value} 
     InsertNodeToTree(&rootNode, &node) 
    } 
    return &rootNode 
} 

Answer 2

tree只是指针的一个副本。分配给变量是没用的。相反，您需要分配给已经存在的节点。例如：

https://play.golang.org/p/Agzby-Yinq

func InsertNodeToTree(tree *TreeNode, node *TreeNode) { 
    if tree == nil { 
     panic("cannot insert into nil root") 
    } 

    if node.Value > tree.Value { 
     if tree.Right == nil { 
      tree.Right = node 
     } else { 
      InsertNodeToTree(tree.Right, node) 
     } 
    } 
    if node.Value < tree.Value { 
     if tree.Left == nil { 
      tree.Left = node 
     } else { 
      InsertNodeToTree(tree.Left, node) 
     } 
    } 
}