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