以前在数据结构的书上学过二叉树的遍历，老师讲了前序、中序、后序遍历三种，但是只是讲了一下概念，在纸上画一下遍历的过程，并没有讲代码的实现。
算法思想
先序遍历
前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始，要一直访问左子树，直到没有左孩子，然后访问右子树。
前序遍历
(图片来自知乎)
理解起来应该是很简单的，不过实现起来就不一样了，图中演示的是用递归的方式遍历的，事实上还可以用迭代来实现，也就是 DFS 和 BFS。
中序遍历
中序遍历
后序遍历
在这个算法演示 的网站上没有找到后序遍历的图，后序遍历的过程就是 左子树-右子树-根节点。
定义树的结构，以下使用的是 golang
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
DFS实现
在遍历二叉树之前先要生成一棵二叉树,可以看到，生成二叉树的过程也是递归的，并且类似这样的代码在很多与二叉树有关的地方都能用到，也可以叫做模板。
递归生成二叉树
package main
import "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]
binary
注意，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
}
公众号：没有梦想的阿巧 后台回复 "群聊"，一起学习，一起进步
网友评论