二叉树的遍历指的是从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。

遍历方式

• 前序遍历：从根节点开始，先遍历左子树，再遍历右子树
• 中序遍历：中序遍历会从左子树最左侧的节点开始，然后从左到右依次遍历左子树，根节点，最后是右子树
• 后序遍历：后序遍历也是从左子树最左侧的节点开始，不过会从左到右先遍历完叶子节点，再遍历父节点，遍历完左子树后，直接从右子树最左侧节点开始，按照和左子树同样的顺序遍历完右子树，最后访问根节点
• 层次遍历：从根节点开始按层次遍历

示例：

二叉树：
         1
        /   \
      2        3
    /  \      \
   4    5      6
       / \
      7   8

遍历结果：
 - 前序遍历：1 2 4 5 7 8 3 6
 - 中序遍历：4 2 7 5 8 1 6 3
 - 后序遍历：4 7 8 5 2 6 3 1
 - 层次遍历：1 2 3 4 5 6 7 8

代码实现

Golang 代码示例：

package main

import (
    "fmt"
)

// 二叉树
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

// 初始化节点
func NewTreeNode(data int) *TreeNode {
    return &TreeNode{
        Val: data,
        Left: nil,
        Right: nil,
    }
}

// 前序遍历
func PreOrderTraverseTreeNode(treeNode *TreeNode) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }

    // 先打印当前节点值
    fmt.Printf("%v ", treeNode.Val)

    // 然后依次对左子树和右子树做前序遍历
    PreOrderTraverseTreeNode(treeNode.Left)
    PreOrderTraverseTreeNode(treeNode.Right)
}

// 中序遍历
func MidOrderTraverseTreeNode(treeNode *TreeNode) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }

    // 先从左子树最左侧节点开始遍历
    MidOrderTraverseTreeNode(treeNode.Left)
    // 打印位于中间的根节点
    fmt.Printf("%v ", treeNode.Val)
    // 最后按照和左子树一样的逻辑遍历右子树
    MidOrderTraverseTreeNode(treeNode.Right)
}

// 后序遍历
func PostOrderTraverseTreeNode(treeNode *TreeNode) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }

    // 先遍历左子树
    PostOrderTraverseTreeNode(treeNode.Left)
    // 再遍历右子树
    PostOrderTraverseTreeNode(treeNode.Right)
    // 最后访问根节点
    fmt.Printf("%v ", treeNode.Val)
}

// 层次遍历
func LevelOrderTraverseTreeNode(treeNode *TreeNode) {
    if nil == treeNode {
        return
    }
    
    tmp := []*TreeNode{treeNode}
    for i := 0; i < len(tmp); i++ {
        current := tmp[i]

        fmt.Printf("%v ", current.Val)

        if nil != current.Left {
            tmp = append(tmp, current.Left)
        }
        if nil != current.Right {
            tmp = append(tmp, current.Right)
        }
    }
}

func main() {
    node1 := NewTreeNode(1) // 根节点
    node2 := NewTreeNode(2)
    node3 := NewTreeNode(3)
    node4 := NewTreeNode(4)
    node5 := NewTreeNode(5)
    node6 := NewTreeNode(6)
    node7 := NewTreeNode(7)
    node8 := NewTreeNode(8)

    node1.Left = node2
    node1.Right = node3
    node2.Left = node4
    node2.Right = node5
    node3.Left = node6
    node4.Left = node7
    node4.Right = node8

    fmt.Print("前序遍历: ")
    PreOrderTraverseTreeNode(node1)
    fmt.Println()

    fmt.Print("中序遍历: ")
    MidOrderTraverseTreeNode(node1)
    fmt.Println()

    fmt.Print("后序遍历: ")
    PostOrderTraverseTreeNode(node1)
    fmt.Println()
    
    fmt.Print("层次遍历: ")
    LevelOrderTraverseTreeNode(node1)
    fmt.Println()
}

运行结果：

前序遍历: 1 2 4 7 8 5 3 6 
中序遍历: 7 4 8 2 5 1 6 3
后序遍历: 7 8 4 5 2 6 3 1
层次遍历: 1 2 3 4 5 6 7 8

【相关推荐】：二叉树简介