CODEWITHSUNDEEP
gotree
user3410960
user3410960

Reputation: 473

How to create a binary tree use struct in golang?

I want to create a binary tree and initialize the tree use golang. And the codes like these:

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

Why the tree's left and right are nil? I pass the reference of the tree node, why not work?

Upvotes: 4

Views: 3793

Answers (2)

Karl Doenitz
Karl Doenitz

Reputation: 2230

In C/C++ programming language, you can use TreeNode *&tree.
But in golang programming language, you can not use *&.
tree is just a copy of the pointer, so you can't point the value to another TreeNode.
I modified your program, and it can run successfully now.
Maybe these codes you need:

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
}

Upvotes: 4

Stephen Weinberg
Stephen Weinberg

Reputation: 53408

tree is only a copy of the pointer. Assigning to the variable is useless. Instead, you need to assign to an already existing node. For example:

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

Upvotes: 4

Related Questions