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

为什么树的左右节点是nil？我传递了树节点的引用，为什么不起作用？

- user3410960

Answer 1

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)
        }
    }
}

- Stephen Weinberg

Answer 2

在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
}

- Karl Doenitz