二叉树遍历

以前在数据结构的书上学过二叉树的遍历,老师讲了前序、中序、后序遍历三种,但是只是讲了一下概念,在纸上画一下遍历的过程,并没有讲代码的实现。
<!--more-->

算法思想

先序遍历

前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始,要一直访问左子树,直到没有左孩子,然后访问右子树。

前序遍历
(图片来自知乎)

理解起来应该是很简单的,不过实现起来就不一样了,图中演示的是用递归的方式遍历的,事实上还可以用迭代来实现,也就是 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
}

公众号:没有梦想的阿巧 后台回复 "群聊",一起学习,一起进步

本文来自:Segmentfault

感谢作者:五行缺金

查看原文:二叉树遍历

• 编辑
• 预览