开发者学堂课程【Go 语言核心编程 - 数据结构和算法： 数据结构和算法-二叉树三种遍历方式】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9869
数据结构和算法-二叉树三种遍历方式
内容介绍
一、二叉树的示意图
二、二叉树的案例
一、二叉树的示意图
1. 定义：
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
我们重点讲解一下二叉树的前序遍历，中序遍历和后序遍历。
二、二叉树的案例
1.使用前序，中序和后序对下面的二叉树进行遍历.
（1）前序遍历：是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
packagemain
import (
"fmt"
）
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//前序遍历【先输出 root 节点，在输出左子树，然后在输出右子树】
func PreOrder(node *Hero) {
if node != nil {
fmt.Printf("no=%d name=%s\n",node.No,node.Name)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
func main(){
//构建一个二叉树
root := &Hero{
No : 1,
Name：“宋江“，
}
left1 := &Hero{
No : 2,
Name："吴用”，
}
right1 := &Hero{
No : 3,
Name："卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No : 4,
Name："林冲",
}
right1.Right = right2
PreOrder(root)
}
（2）思考：
这回输出顺序为“宋江”，“吴用”，“10”，“12”，“卢俊义”，“林冲”。
（3）中序遍历：是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
packagemain
import (
"fmt"
）
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//中序遍历[先输出 root 的左子树，再输 root 的右子树，最后输出 root 的节点]
func InfixOrder(node *Hero) {
if node != nil {
InfixOrder(node.Left)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
InfixOrder(node.Right)
}
}
func main(){
//构建一个二叉树
root := &Hero{
No : 1,
Name：“宋江“，
}
left1 := &Hero{
No : 2,
Name："吴用”，
}
right1 := &Hero{
No : 3,
Name："卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No : 4,
Name："林冲",
}
right1.Right = right2
//PreOrder(root)
InfixOrder(root)
}
（4）后序遍历：是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
package main
import (
"fmt"
）
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//后序遍历[先输出 root 的左子树，再输 root 结点，最后输出 root 的右子树]
func PostOrder(node *Hero) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
}
}
func main(){
//构建一个二叉树
root := &Hero{
No : 1,
Name：“宋江“，
}
left1 := &Hero{
No : 2,
Name："吴用”，
}
right1 := &Hero{
No : 3,
Name："卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No : 4,
Name："林冲",
}
right1.Right = right2
//PreOrder(root)
InfixOrder(root)
}
