doudou3213 2019-07-01 23:39
浏览 102
已采纳

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

I am trying to implement a simple binary tree in Golang in order to understand concepts being taught in class.

I'm a bit new to Golang but at the same time, I'm having a hard time wrapping my head around the concepts of recursion and where to insert the next node.

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

The output I am getting is:

added to the right
added to the left
added to the right
|6|

The expected output should be:

added to the right
added to the left
recurse
added to the right
4 6 8 10

Any help is greatly appreciated.

  • 写回答

1条回答 默认 最新

  • duanfu1873 2019-07-02 00:13
    关注

    This code will insert duplicate on the right. You may want to ignore duplicates (with commented out line).

    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)
            }
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题