介绍

当我们介绍数组、链表时，为什么没有着重研究他们的遍历过程呢？ 二叉树的遍历又有什么特殊之处？

在计算机程序中，遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。

反观二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。

那么，二叉树都有哪些遍历方式呢？

从节点之间位置关系的角度来看，二叉树的遍历分为4种。

1. 前序遍历。

2. 中序遍历。

3. 后序遍历。

4. 层序遍历。

从更宏观的角度来看，二叉树的遍历归结为两大类。

1. 深度优先遍历 （前序遍历、中序遍历、后序遍历）。

2. 广度优先遍历 （层序遍历）。

下面就来具体看一看这些不同的遍历方式。

深度优先遍历

深度优先和广度优先这两个概念不止局限于二叉树，它们更是一种抽象的算法思想，决定了访问某些复杂数据结构的顺序。在访问树、图，或其他一些复杂数据结构时，这两个概念常常被使用到。

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。可能这种说法有些抽象，下面就通过二叉树的前序遍历、中序遍历、后序遍历 ，来看一看深度优先是怎么回事吧。

前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树。

上图就是一个二叉树的前序遍历，每个节点左侧的序号代表该节点的输

出顺序，详细步骤如下。

1. 首先输出的是根节点1。
2. 由于根节点1存在左孩子，输出左孩子节点2。
3. 由于节点2也存在左孩子，输出左孩子节点4。
4. 节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5。
5. 节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的 右孩子节点3。
6. 节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6。到此为止，所有的节点都遍历输出完毕。

中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树。

上图就是一个二叉树的中序遍历，每个节点左侧的序号代表该节点的输出顺序，详细步骤如下。

1. 首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2. 依照中序遍历的次序，接下来输出节点4的父节点2。
3. 再输出节点2的右孩子节点5。
4. 以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1。
5. 由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3。
6. 最后输出节点3的右孩子节点6。

到此为止，所有的节点都遍历输出完毕。

后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

二叉树的前序、中序、后序遍历的代码怎么写呢？ 递归实现

package net.csdn.usermedal.controller;

import org.apache.commons.collections4.CollectionUtils;

import java.util.LinkedList;

/**
 * Created by haoll on 2022/5/13
 */
public class Demo {

    /**
     * 二叉树类
     */
    public static class TreeNode{
        private int data;

        private TreeNode leftNode;

        private TreeNode rightNode;

        public TreeNode(int data){
            this.data = data;
        }
    }

    /**
     * 构建二叉树
     * @param inputList
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList inputList){
        TreeNode node = null;
        if(CollectionUtils.isEmpty(inputList)){
            return null;
        }
        Integer data = inputList.removeFirst();
        if(data != null){
            node = new TreeNode(data);
            node.leftNode = createBinaryTree(inputList);
            node.rightNode = createBinaryTree(inputList);
        }
        return node;
    }

    /**
     * 二叉树的前序遍历，输出顺序是根节点、左子树、右子树。
     * @param treeNode
     */
    public static void  preOrderTraveral(TreeNode treeNode){
        if(treeNode == null){
            return ;
        }
        System.out.println(treeNode.data);
        preOrderTraveral(treeNode.leftNode);
        preOrderTraveral(treeNode.rightNode);
    }

    /**
     * 二叉树的中序遍历，输出顺序是左子树、根节点、右子树。
     * @param treeNode
     */
    public static void inOrderTraveral(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        inOrderTraveral(treeNode.leftNode);
        System.out.println(treeNode.data);
        inOrderTraveral(treeNode.rightNode);
    }

    /**
     * 二叉树的后序遍历，输出顺序是左子树、右子树、根节点
     * @param treeNode
     */
    public static void  postOrderTraveral(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        postOrderTraveral(treeNode.leftNode);
        postOrderTraveral(treeNode.rightNode);
        System.out.println(treeNode.data);

    }


    public static void main(String[] args) {
       
        LinkedList inputList = new LinkedList (Arrays. asList(new Integer[]{3,2,9,null,null,10,null, null,8,null,4}));
        
        TreeNode binaryTree = createBinaryTree(inputList);
        System.out.println(binaryTree);

        System.out.println("前序遍历");
        preOrderTraveral(binaryTree);

        System.out.println("中序遍历");
        inOrderTraveral(binaryTree);

        System.out.println("后序遍历");
        postOrderTraveral(binaryTree);
    }
}

二叉树用递归方式来实现前序、中序、后序遍历，是最为自然的方式，因此代码也非常简单。

这3种遍历方式的区别，仅仅是输出的执行位置不同：前序遍历的输出在前，中序遍历的输出在中间，后序遍历的输出在最后。

代码中值得注意的一点是二叉树的构建。二叉树的构建方法有很多，这里把一个线性的链表转化成非线性的二叉树，链表节点的顺序恰恰是二叉树前序遍历的顺序。链表中的空值，代表二叉树节点的左孩子或右孩子为空的情况。

在代码的main函数中，通过{3,2,9,null,null,10,null,null,8,null,4}这样一个线性序列，构建成的二叉树如下。

除使用递归以外，二叉树的深度优先遍历还能通过非递归的方式来实现，不过要稍微复杂一些。

绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解 决，这种数据结构就是栈 。因为递归和栈都有回溯的特性。

如何借助栈来实现二叉树的非递归遍历呢？下面以二叉树的前序遍历为例，看一看具体过程。

1. 首先遍历二叉树的根节点1，放入栈中。

2. 遍历根节点1的左孩子节点2，放入栈中。

3. 遍历节点2的左孩子节点4，放入栈中。

4. 节点4既没有左孩子，也没有右孩子，我们需要回溯到上一个节点2。 可是现在并不是做递归操作，怎么回溯呢？

别担心，栈已经存储了刚才遍历的路径。让旧的栈顶元素4出栈，就可以重新访问节点2，得到节点2的右孩子节点5。

此时节点2已经没有利用价值（已经访问过左孩子和右孩子），节点2出栈，节点5入栈。

5. 节点5既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点1。所以让节点5出栈。 根节点1的右孩子是节点3，节点1出栈，节点3入栈。

6. 节点3的右孩子是节点6，节点3出栈，节点6入栈。

7. 节点6既没有左孩子，也没有右孩子，所以节点6出栈。此时栈为空，遍历结束。

代码实现

public static void preOrderTraveralWithStack(TreeNode root){
        Stack stack = new Stack<>();
        TreeNode treeNode = root;
        //迭代访问节点的左孩子，并入栈
        while (treeNode != null || !stack.isEmpty()){
            while (treeNode != null){
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftNode;
            }
            //没有左孩子了，弹出栈顶，访问右孩子
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.rightNode;
            }
        }
    }

广度优先遍历

如果说深度优先遍历是在一个方向上“一头扎到底”，那么广度优先遍历 则恰恰相反：先在各个方向上各走出1步，再在各个方向上走出第2步、第3步……一直到各个方向全部走完。听起来有些抽象，下面让我们通 过二叉树的层序遍历 ，来看一看广度优先是怎么回事。

层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关 系，一层一层横向遍历各个节点。

上图就是一个二叉树的层序遍历，每个节点左侧的序号代表该节点的输出顺序。 可是，二叉树同一层次的节点之间是没有直接关联的，如何实现这种层序遍历呢

这里同样需要借助一个数据结构来辅助工作，这个数据结构就是队列 。

详细遍历步骤如下。

1. 根节点1进入队列。

2. 节点1出队，输出节点1，并得到节点1的左孩子节点2、右孩子节点 3。让节点2和节点3入队。

3. 节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点 5。让节点4和节点5入队。

4. 节点3出队，输出节点3，并得到节点3的右孩子节点6。让节点6入队。

5. 节点4出队，输出节点4，由于节点4没有孩子节点，所以没有新节点 入队。

6. 节点5出队，输出节点5，由于节点5同样没有孩子节点，所以没有新节点入队。

7. 节点6出队，输出节点6，节点6没有孩子节点，没有新节点入队。到此为止，所有的节点遍历输出完毕。

代码实现

 public static void levelOrderTraversal(TreeNode treeNode){
        Queue queue = new LinkedList<>();
        queue.offer(treeNode);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            System.out.println(poll.data);
            if(poll.leftNode != null){
                queue.offer(poll.leftNode);
            }
            if(poll.rightNode != null){
                queue.offer(poll.rightNode);
            }
        }
    }