代码:树的3种遍历

package main

import (
	"fmt"
)

type node struct {
	Val string
	Left *node
	Right *node
}

type bst struct {
	root *node
}

/*
     m
   k   l
 h   i   j
a b c d e f
*/

func (tree *bst) buildTree() {
	m := &node{Val: "m"}
	tree.root = m

	k := &node{Val: "k"}
	l := &node{Val: "l"}
	m.Left = k
	m.Right = l

	h := &node{Val: "h"}
	i := &node{Val: "i"}
	k.Left = h
	k.Right = i

	a := &node{Val: "a"}
	b := &node{Val: "b"}
	h.Left = a
	h.Right = b

	c := &node{Val: "c"}
	d := &node{Val: "d"}
	i.Left = c
	i.Right = d

	j := &node{Val: "j"}
	l.Right = j

	e := &node{Val: "e"}
	f := &node{Val: "f"}
	j.Left = e
	j.Right = f
}

// 先序遍历（根左右）：m k h a b i c d l j e f
func (tree *bst) inOrder() []string {
	res := make([]string, 0)
	var inner func(n *node)
	inner = func(n *node) {
		if n == nil {
			return
		}
		res = append(res, n.Val)
		inner(n.Left)
		inner(n.Right)
	}
	inner(tree.root)
	return res
}

// 中序遍历（左根右）：a h b k c i d m l e j f
func (tree *bst) midOrder() []string {
	res := make([]string, 0)
	var inner func(n *node)
	inner = func(n *node) {
		if n == nil {
			return
		}
		inner(n.Left)
		res = append(res, n.Val)
		inner(n.Right)
	}
	inner(tree.root)
	return res
}

// 后序遍历（左右根）：a b h c d i k e f j l m
func (tree *bst) lastOrder() []string {
	res := make([]string, 0)
	var inner func(n *node)
	inner = func(n *node) {
		if n == nil {
			return
		}
		inner(n.Left)
		inner(n.Right)
		res = append(res, n.Val)
	}
	inner(tree.root)
	return res
}

func main() {
	tree := &bst{}
	tree.buildTree()
	fmt.Println(tree.inOrder())
	fmt.Println(tree.midOrder())
	fmt.Println(tree.lastOrder())
}

结果:
/private/var/folders/fw/md_z65fd6sb4jsxc2sjy358h0000gn/T/___go_build_go_english_a
[m k h a b i c d l j e f]
[a h b k c i d m l e j f]
[a b h c d i k e f j l m]