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

Question

我正在尝试在 Golang 中实现一个简单的二叉树，以便理解课堂上教授的概念。

我对 Golang 有点陌生，但同时，我很难理解递归的概念以及在哪里插入下一个节点。

package main

import "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 right

added to the left

added to the right

|6|

预期输出应该是：

added to the right

added to the left

recurse

added to the right

4 6 8 10

任何帮助是极大的赞赏。

Answer 1

此代码将在右侧插入重复项。您可能想忽略重复项（带有注释掉的行）。func (n *Node) insert(newNode *Node){&nbsp; &nbsp; if newNode.data < n.data {&nbsp; &nbsp; &nbsp; &nbsp; if n.left == nil {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n.left = newNode&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n.left.insert(newNode)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } else {&nbsp; &nbsp; //} else if newNode.data > n.data {&nbsp; &nbsp; &nbsp; &nbsp; if n.right == nil {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n.right = newNode&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n.right.insert(newNode)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}