如何在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) 
     } 
    } 
}