Go Binary Tree Traversal


          a
         / \
        b   c
       / \
      d   f
     /   /
    e   g

Preorder: a → b → d → e → f → g → c
Inorder: e → d → b → g → f → a → c
Postorder: e → d → g → f → b → c → a

Traversal a binary tree recursively

package main

import "fmt"

type Node struct {
    data        string
    left, right *Node
}

func main() {
    nodeG := Node{data: "g", left: nil, right: nil}
    nodeF := Node{data: "f", left: &nodeG, right: nil}
    nodeE := Node{data: "e", left: nil, right: nil}
    nodeD := Node{data: "d", left: &nodeE, right: nil}
    nodeC := Node{data: "c", left: nil, right: nil}
    nodeB := Node{data: "b", left: &nodeD, right: &nodeF}
    nodeA := Node{data: "a", left: &nodeB, right: &nodeC}
    fmt.Println("Preorder")
    nodeA.PrintPre()
    fmt.Println("Inorder")
    nodeA.PrintIn()
    fmt.Println("Postorder")
    nodeA.PrintPost()
}

// Preorder (Root, Left, Right)
func (root *Node) PrintPre() {
    fmt.Println(root.data)
    if root.left != nil {
        root.left.PrintPre()
    }
    if root.right != nil {
        root.right.PrintPre()
    }
}

// Inorder (Left, Root, Right)
func (root *Node) PrintIn() {
    if root.left != nil {
        root.left.PrintIn()
    }
    fmt.Println(root.data)
    if root.right != nil {
        root.right.PrintIn()
    }
}

// Postorder (Left, Right, Root)
func (root *Node) PrintPost() {
    if root.left != nil {
        root.left.PrintPost()
    }
    if root.right != nil {
        root.right.PrintPost()
    }
    fmt.Println(root.data)
}

Traversal a binary tree without recursively

type seqStack struct {
    data [100]*Node
    tag  [100]int
    top  int // array index
}

// Preorder traversal without recursively
func (node *Node) preOrderLoop() (result []string) {
    var s seqStack
    s.top = -1 // nil
    if node == nil {
        panic("no data here")
    } else {
        for node != nil || s.top != -1 {
            for node != nil {
                result = append(result, node.data)
                s.top++
                s.data[s.top] = node
                node = node.left
            }
            s.top--
            node = s.data[s.top+1]
            node = node.right
        }
    }
    return
}

// Inorder traversal without recursively
func (node *Node) inOrderLoop() (result []string) {
    var s seqStack
    s.top = -1 // nil
    if node == nil {
        panic("no data here")
    } else {
        for node != nil || s.top != -1 {
            for node != nil {
                s.top++
                s.data[s.top] = node
                node = node.left
            }
            s.top--
            node = s.data[s.top+1]
            result = append(result, node.data)
            node = node.right
        }
    }
    return
}

// Postorder traversal without recursively
func (node *Node) postOrderLoop() (result []string) {
    var s seqStack
    s.top = -1
    if node == nil {
        panic("no data here")
    } else {
        for node != nil || s.top != -1 {
            for node != nil {
                s.top++
                s.data[s.top] = node
                s.tag[s.top] = 0
                node = node.left
            }
            if s.tag[s.top] == 0 {
                node = s.data[s.top]
                s.tag[s.top] = 1
                node = node.right
            } else {
                for s.tag[s.top] == 1 {
                    s.top--
                    node = s.data[s.top+1]
                    result = append(result, node.data)
                    if s.top < 0 {
                        break
                    }
                }
                node = nil
            }
        }
    }
    return
}
0.00 avg. rating (0% score) - 0 votes