Go 数据结构和算法篇（十六）：二叉树的遍历

xueyuanjun

共 4380字，需浏览 9分钟

· 2021-07-30

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

有多种方式可以遍历二叉树，如果按照从左到右的习惯方式，主要分为三种：前序遍历、中序遍历和后序遍历。下面我们简单介绍这几种遍历方式及对应实现算法，所谓的前序、中序和后序都是以根节点作为参照系。

一、前序遍历

从根节点开始，先遍历左子树，再遍历右子树（对于子树的子树，依此类推），如果二叉树为空，则返回空：

显然，我们可以通过递归来实现二叉树的前序遍历逻辑，对应的 Go 实现代码如下：

package main

import (
    "fmt"
)

// Node 通过链表存储二叉树节点信息
type Node struct {
    Data  interface{}
    Left  *Node
    Right *Node
}

func NewNode(data interface{}) *Node {
    return &Node{
        Data:  data,
        Left:  nil,
        Right: nil,
    }
}

func (node *Node) GetData() string {
    return fmt.Sprintf("%v", node.Data)
}

// 前序遍历
func preOrderTraverse(treeNode *Node) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }
    // 否则先打印当前节点值
    fmt.Printf("%s ", treeNode.GetData())
    // 然后对左子树和右子树做前序遍历
    preOrderTraverse(treeNode.Left)
    preOrderTraverse(treeNode.Right)
}

// 测试代码
func main() {
    // 初始化一个简单的二叉树
    node1 := NewNode(0) // 根节点
    node2 := NewNode("1")
    node3 := NewNode(2.0)
    node1.Left = node2
    node1.Right = node3

    // 前序遍历这个二叉树
    fmt.Print("前序遍历: ")
    preOrderTraverse(node1)
    fmt.Println()
}

这里，我们使用了链表结构来存储二叉树，并且通过 interface{} 空接口类型声明二叉树节点支持存储任意类型数据。

执行上述代码，打印结果如下：

二、中序遍历

中序遍历会从左子树最左侧的节点开始，然后从左到右依次遍历左子树，根节点，最后是右子树（依然是从最左侧节点开始从左到右的顺序遍历），如果二叉树为空，则返回空：

我们在上面的示例代码中添加中序遍历实现代码：

package main

import (
    "fmt"
)

...

// 中序遍历
func midOrderTraverse(treeNode *Node) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }
    // 否则先从左子树最左侧节点开始遍历
    midOrderTraverse(treeNode.Left)
    // 打印位于中间的根节点
    fmt.Printf("%s ", treeNode.GetData())
    // 最后按照和左子树一样的逻辑遍历右子树
    midOrderTraverse(treeNode.Right)
}

func main() {
    ...

    // 中序遍历这个二叉树
    fmt.Print("中序遍历: ")
    midOrderTraverse(node1)
    fmt.Println()
}

执行上述代码，打印结果如下：

三、后序遍历

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

有了前面的基础，编写后序遍历实现代码就相当轻松了：

package main

import (
    "fmt"
)

...

// 后序遍历
func postOrderTraverse(treeNode *Node) {
    // 节点为空则退出当前递归
    if treeNode == nil {
        return
    }
    // 否则先遍历左子树
    postOrderTraverse(treeNode.Left)
    // 再遍历右子树
    postOrderTraverse(treeNode.Right)
    // 最后访问根节点
    fmt.Printf("%s ", treeNode.GetData())
}

func main() {
    ...

    // 后序遍历这个二叉树
    fmt.Print("后序遍历: ")
    postOrderTraverse(node1)
    fmt.Println()
}