Как реализовать обход Inorder в бинарном дереве в Голанге - PullRequest
Новая
       67

Как реализовать обход Inorder в бинарном дереве в Голанге

0 голосов
/ 02 июля 2019

Я пытаюсь реализовать простое двоичное дерево на Голанге, чтобы понять концепции, которым обучают в классе.

Я немного новичок в 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

Любая помощь очень ценится.

1 Ответ

1 голос
/ 02 июля 2019

Этот код вставит дубликаты справа.Вы можете игнорировать дубликаты (с закомментированной строкой). 

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