以前在数据结构的书上学过二叉树的遍历，老师讲了前序、中序、后序遍历三种，然而只是讲了一下概念，在纸上画一下遍历的过程，并没有讲代码的实现。
<!--more-->
算法思维
先序遍历
前序遍历的程序是 根节点-左子树-右子树 。意思是从根节点开始，要始终拜访左子树，直到没有左孩子，而后拜访右子树。
(图片来自知乎)
了解起来应该是很简略的，不过实现起来就不一样了，图中演示的是用递归的形式遍历的，事实上还能够用迭代来实现，也就是 DFS 和 BFS。
中序遍历
后序遍历
在这个算法演示 的网站上没有找到后序遍历的图，后序遍历的过程就是 左子树-右子树-根节点。
定义树的构造，以下应用的是 golang
type TreeNode struct { Val int Left *TreeNode Right *TreeNode}DFS实现
在遍历二叉树之前先要生成一棵二叉树,能够看到，生成二叉树的过程也是递归的，并且相似这样的代码在很多与二叉树无关的中央都能用到，也能够叫做模板。
递归生成二叉树
package mainimport "fmt"type TreeNode struct { Val int Left *TreeNode Right *TreeNode}func main() { root := &TreeNode{} dfs(root, 1) fmt.Println(root.Left)}func dfs(p *TreeNode, depth int) { if depth < 3 { left := &TreeNode{Val: 2 * depth} right := &TreeNode{Val: 4 * depth} p.Left = left p.Right = right dfs(p.Left, depth+1) dfs(p.Right, depth+1) }}接下来才是遍历二叉树
func dfsbr(p *TreeNode, res *[]int) { if p != nil { *res = append(*res, p.Val) dfsbr(p.Left, res) dfsbr(p.Right, res) }}先拜访左孩子节点，再拜访右孩子节点，这就是先序遍历了。看一下打印进去的后果
$ go run main.go[0 2 4 8 4 4 8]留神，golang 在root 初始化的时候会默认给 root 赋值，Val 的类型为 int ，因而初值为 0。比照一下二叉树和打印进去的节点，是合乎 根节点-左子树-右子树 这个过程的。
对于后序遍历和中序遍历的递归实现其实是一样的，只是把递归的程序变换了一下而已。
中序遍历
func dfsbr(p *TreeNode, res *[]int) { if p != nil { dfsbr(p.Left, res) *res = append(*res, p.Val) dfsbr(p.Right, res) }}后序遍历
func dfsbr(p *TreeNode, res *[]int) { if p != nil { dfsbr(p.Left, res) dfsbr(p.Right, res) *res = append(*res, p.Val) }}BFS实现
在 DFS 中，是应用的递归的形式查找，程序运行过程中的数据会保留在零碎栈里。而应用 BFS 须要本人创立一个队列，保留程序运行中途的信息。
层序遍历
func bfs(p *TreeNode) []int { res := make([]int, 0) if p == nil { return res } queue := []*TreeNode{p} for len(queue) > 0 { length := len(queue) for length > 0 { length-- if queue[0].Left != nil { queue = append(queue, queue[0].Left) } if queue[0].Right != nil { queue = append(queue, queue[0].Right) } res = append(res, queue[0].Val) queue = queue[1:] } } return res}打印后果
$ go run main.go [0 2 4 4 8 4 8]能够看到，层序遍历的后果和上图中画进去的二叉树是一一对应的。
先序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func preorderTraversal(root *TreeNode) []int { result := make([]int, 0) if root == nil { return result } queue := make([]*TreeNode, 0) for len(queue) > 0 || root != nil { for root != nil { result = append(result, root.Val) queue = append(queue, root) root = root.Left } root = queue[len(queue) - 1].Right queue = queue[:len(queue) - 1] } return result}中序遍历
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func inorderTraversal(root *TreeNode) []int { result := make([]int, 0) if root == nil { return result } queue := make([]*TreeNode, 0) for len(queue) > 0 || root != nil { for root != nil { queue = append(queue, root) root = root.Left } node := queue[len(queue) - 1] queue = queue[:len(queue) - 1] result = append(result, node.Val) root = node.Right } return result}后序遍历
func postorderTraversal(root *TreeNode) []int { result := make([]int, 0) if root == nil { return result } queue := make([]*TreeNode, 0) var lastVisited *TreeNode for len(queue) > 0 || root != nil{ for root != nil { queue = append(queue, root) root = root.Left } n := queue[len(queue) - 1] if n.Right == nil || n.Right == lastVisited { result = append(result, n.Val) queue = queue[:len(queue) - 1] lastVisited = n } else { root = n.Right } } return result}公众号：没有幻想的阿巧 后盾回复 "群聊"，一起学习，一起提高