二叉树遍历（前序遍历、中序遍历、后序遍历、层序遍历）

二叉树

概述

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。每个节点包含一个值，该值可能是任何类型，具体取决于树的应用。二叉树有许多不同的类型和变体，包括二叉搜索树（BST）、平衡二叉树（AVL树、红黑树等）、堆等。二叉树在计算机科学中广泛应用，包括数据库索引、编译器中的语法树、网络路由等领域，MySQL数据库就是是用B+树作为索引的数据结构。

今天主要说一下二叉树的遍历，遍历二叉树主要有三种方式：前序遍历、中序遍历和后序遍历。

因为普通的二叉树通常会有三个节点组合而成，前、中、后这三个字说明的根节点在三个节点中遍历的顺序。

我们看一下下面这颗二叉树的几种遍历顺序

    1
   / 
  2   
 / \
3   4
   / \
  5   7
   \
    6

前：1 2 3 4 5 6 7

中：3 2 5 6 4 7 1

后：3 6 5 7 4 2 1

层次遍历（广度遍历）：1 2 3 4 5 7 6

深度遍历：1 2 3 4 5 6 7

递归实现前、中、后遍历

递归实现的代码最简单，也是理解二叉树遍历最好的方法，下面是二叉树节点的结构TreeNode 类和二叉树类，二叉树类中有一个构建二叉树的方法createBinaryTree

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

public class BinaryTree {
    public static TreeNode createBinaryTree(LinkedList<Integer> list) {
        TreeNode treeNode = null;
         if (list == null || list.size() == 0) {
             return null;
         }
        Integer first = list.removeFirst();
         if (first != null) {
             treeNode = new TreeNode(first);
             treeNode.left = createBinaryTree(list);
             treeNode.right = createBinaryTree(list);
         }
        return treeNode;
    }
}

遍历代码

//这一看就懂,多简单的代码
//没找到感觉的话，打着断点走一遍,门清!
public static void preOrderBinaryTree(TreeNode treeNode) {
    if (treeNode!= null) {
        System.out.print(treeNode.data+" ");
        preOrderBinaryTree(treeNode.left);
        preOrderBinaryTree(treeNode.right);
    }
}
public static void inOrderBinaryTree(TreeNode treeNode) {
    if (treeNode!= null) {
        inOrderBinaryTree(treeNode.left);
        System.out.print(treeNode.data+" ");
        inOrderBinaryTree(treeNode.right);
    }

}
public static void postBinaryTree(TreeNode treeNode) {
    if (treeNode!= null) {
        postBinaryTree(treeNode.left);
        postBinaryTree(treeNode.right);
        System.out.print(treeNode.data+" ");
    }
}

//测试方法
public static void main(String[] args) {
    LinkedList<Integer> inputList1 = new LinkedList<>(Arrays.asList(new Integer[]{1,2, 3, null, null, 4,5, null, 6,null,  null, 7,null,null}));

    TreeNode treeNode = createBinaryTree(inputList1);
    preOrderBinaryTree(treeNode);
    System.out.println();

    inOrderBinaryTree(treeNode);
    System.out.println();

    postBinaryTree(treeNode);
}

非递归遍历

非递归遍历，就有点意思了，为了回过头遍历，需要用栈来保存之前遍历过的节点，还是之前这颗树，我们来看看它的前序遍历如何实现

    1
   / 
  2   
 / \
3   4
   / \
  5   7
   \
    6

前序遍历

第一次遇到该节点遍历，在入栈的时候就输出节点的值

public static void stackPreOrderBinaryTree(TreeNode treeNode) {
    Stack<TreeNode> objects = new Stack<>();
    while (!(treeNode == null && objects.isEmpty())) {
        if (treeNode == null) {
            treeNode = objects.pop();
            treeNode = treeNode.right;
        } else {
            objects.push(treeNode);
            //入栈的时候遍历
            System.out.print(treeNode.data + " ");
            treeNode = treeNode.left;
        }
    }
}

中序遍历

第二次遇到该节点遍历，在出栈的时候就输出节点的值

public static void stackInOrderBinaryTree(TreeNode treeNode) {
    Stack<TreeNode> objects = new Stack<>();
    while (!(treeNode == null && objects.isEmpty())) {
        if (treeNode != null) {
            objects.push(treeNode);
            //指向左节点
            treeNode = treeNode.left;
        } else {
            treeNode = objects.pop();
            //出栈的时候遍历
            System.out.print(treeNode.data + " ");
            treeNode = treeNode.right;
        }
    }
}

后序遍历

后序遍历是第三次遇到该节点再遍历，但是栈只能给我们提供遇到两次的判断方法，第一次是入栈时，第二次是出栈时，它们分别对应着二叉树的先序和中序遍历。所以我们需要利用一些技巧来辅助我们判断，这也是后序遍历二叉树比先序和中序稍微复杂一点的原因。

public static void stackPostOrderBinaryTree(TreeNode treeNode) {
    // 创建一个栈用于模拟递归调用
    Stack<TreeNode> stack = new Stack<>();
    // 用于记录上一个访问的节点
    TreeNode pre = null;
    // 当当前节点不为空或者栈不为空时循环进行后序遍历
    while (treeNode != null || stack.size() != 0) {
        // 遍历左子树并将路径上的节点压入栈中
        while (treeNode != null) {
            stack.push(treeNode);
            treeNode = treeNode.left;
        }
        // 弹出栈顶节点
        treeNode = stack.pop();
        // 如果右子树为空或者右子树已经被访问过，则可以访问当前节点
        if (treeNode.right == null || treeNode.right == pre) {
            // 更新pre为当前节点
            pre = treeNode;
            // 输出当前节点的值
            System.out.print(treeNode.data + " ");
            // 将treeNode置为null，表示下次循环需要从栈中取出新的节点
            treeNode = null;
        } else {  
            // 如果右子树不为空且未被访问过，则将当前节点重新压入栈中
            stack.push(treeNode);
            // 将treeNode指向右子树，继续遍历右子树
            treeNode = treeNode.right;
        }
    }
}

层次遍历

使用队列来辅助遍历，可以轻松实现二叉树的层次遍历。首先让根节点入队，如果节点的左右子节点不为空，让节点轮流入队，之后遍历队列中poll出的节点就可以了

public static void queueLevelOrderBinaryTree(TreeNode treeNode) {
    Queue<TreeNode> treeNodes = new LinkedBlockingDeque<>();
    treeNodes.add(treeNode);
    while (!treeNodes.isEmpty()){
        treeNode = treeNodes.poll();
        System.out.println(treeNode.data);
        if (treeNode.left!=null){
            treeNodes.add(treeNode.left);
        }
        if (treeNode.right!=null){
            treeNodes.add(treeNode.right);
        }
    }
}

总结

整理了一下二叉树的几种遍历方式，递归遍历实现起来比较简单，也很容易理解前中后三种遍历规则。熟练掌握遍历规则后可以用非递归的方式来实现，非递归方式可以增加我们对栈特性的理解，入栈、出栈对应着前序和中序，后序遍历是第三次经过节点才输出，我们用pre帮助我们记录节点信息。层次遍历用队列做辅助，可以轻松实现。