如何在Golang中实现二叉树的中序遍历

Question

我正在尝试在 Golang 中实现一个简单的二叉树，以便理解课堂上教授的概念。我对 Golang 有点陌生，但同时，我很难理解递归的概念以及在哪里插入下一个节点。package mainimport "fmt"type Node struct {    data int    right *Node    left *Node}func main(){    //driver code    //this is the root of the tree    root := Node{data:6}    //set the data to the int    //set the right and left pointers to null    /*     6   /   \ nil   nil */ n1 := Node{data: 8} n2 := Node{data: 4} n3 := Node{data: 10} root.insert(&n1) root.insert(&n2) root.insert(&n3) inorder(&root)}func (n *Node) insert(newNode *Node){    if n.left == nil && newNode.data < n.data {        fmt.Println("added to the left")    }else if n.right == nil && newNode.data > n.data {        fmt.Println("added to the right")    }else{        print("recurse")        n.insert(newNode)    }}func inorder(rt *Node){    if rt == nil {        fmt.Print("|")        return    }    inorder(rt.left)    fmt.Print(rt.data)    inorder(rt.right)}我得到的输出是：added to the rightadded to the leftadded to the right|6|预期输出应该是：added to the rightadded to the leftrecurseadded to the right4 6 8 10任何帮助是极大的赞赏。

Answer 1

此代码将在右侧插入重复项。您可能想忽略重复项（带有注释掉的行）。

func (n *Node) insert(newNode *Node){

    if newNode.data < n.data {

        if n.left == nil {

            n.left = newNode

        } else {

            n.left.insert(newNode)

        }

    } else {

    //} else if newNode.data > n.data {

        if n.right == nil {

            n.right = newNode

        } else {

            n.right.insert(newNode)

        }

    }

}