72 lines
1.5 KiB
Go
72 lines
1.5 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
// flat, level-order representation.
|
|
// for node at index k, left child has index 2k, right child has index 2k+1.
|
|
// a value of -1 means the node does not exist.
|
|
type tree []int
|
|
|
|
func main() {
|
|
t := tree{1, 2, 3, 4, 5, 6, -1, 7, -1, -1, -1, 8, 9}
|
|
visitor := func(n int) {
|
|
fmt.Print(n, " ")
|
|
}
|
|
fmt.Print("preorder: ")
|
|
t.iterPreorder(visitor)
|
|
fmt.Print("\ninorder: ")
|
|
t.iterInorder(visitor)
|
|
fmt.Print("\npostorder: ")
|
|
t.iterPostorder(visitor)
|
|
fmt.Print("\nlevel-order: ")
|
|
t.iterLevelorder(visitor)
|
|
fmt.Println()
|
|
}
|
|
|
|
func (t tree) iterPreorder(visit func(int)) {
|
|
var traverse func(int)
|
|
traverse = func(k int) {
|
|
if k >= len(t) || t[k] == -1 {
|
|
return
|
|
}
|
|
visit(t[k])
|
|
traverse(2*k + 1)
|
|
traverse(2*k + 2)
|
|
}
|
|
traverse(0)
|
|
}
|
|
|
|
func (t tree) iterInorder(visit func(int)) {
|
|
var traverse func(int)
|
|
traverse = func(k int) {
|
|
if k >= len(t) || t[k] == -1 {
|
|
return
|
|
}
|
|
traverse(2*k + 1)
|
|
visit(t[k])
|
|
traverse(2*k + 2)
|
|
}
|
|
traverse(0)
|
|
}
|
|
|
|
func (t tree) iterPostorder(visit func(int)) {
|
|
var traverse func(int)
|
|
traverse = func(k int) {
|
|
if k >= len(t) || t[k] == -1 {
|
|
return
|
|
}
|
|
traverse(2*k + 1)
|
|
traverse(2*k + 2)
|
|
visit(t[k])
|
|
}
|
|
traverse(0)
|
|
}
|
|
|
|
func (t tree) iterLevelorder(visit func(int)) {
|
|
for _, n := range t {
|
|
if n != -1 {
|
|
visit(n)
|
|
}
|
|
}
|
|
}
|