二叉树遍历笔记 (先序、中序、后序)

前言

本篇博文包含以下知识点：

涉及二叉树的先序、中序、后序的递归和非递归遍历。

二叉树具有以下特点：

每个节点最多有两颗子树，节点的度最大为2。
左子树和右子树是是有顺序的，次序不能颠倒。
即使某节点只有一个子树，也要区分左右子树。

无论哪种遍历方法，对节点的考察顺序都是一样的，只是有时候考察了节点，先暂存，在之后的过程输出。

先序：考察到一个节点后，即刻输出该节点的值，并继续遍历其左右树。（根节点->左子树->右子树）

中序：考察到一个节点后将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。（左子树->根节点->右子树）

后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。（左子树->右子树->根节点）

遍历(Traversal)：是指沿着某条搜索路线，一次对树中每个节点均做一次且仅做一次访问。

二叉树节点类：

树节点：

public class TreeNode {
    int val;
    //左子树
    TreeNode left;
    //右子树
    TreeNode right;

    //构造方法
    TreeNode(int x) {
        val = x;
    }
}

一、先序遍历(Preorder Traversal)

递归先序遍历：

先输出节点的值，再递归遍历左右子树。

//递归先序遍历
public static void recursionPreorderTraversal(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + "");
        recursionPreorderTraversal(root.left);
        recursionPreorderTraversal(root.right);
    }
}

非递归先序遍历:

在遍历完节点的左子树后要接着遍历节点的右子树，为了能找到该节点，需要使用栈来进行暂存。

 //非递归遍历
public static void preorderTraversal(TreeNode root) {
        //用来暂存节点的栈
        Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
        //新建一个游标节点为根节点；
        TreeNode node = root;
        //当节点非空，或者栈非空的时候，进入循环
        //当遍历到最后一个节点，其左右子树都为空，且栈也为空，不满足循环条件
        while (node != null || !treeNodeStack.isEmpty()) {
            while (node != null) {
                //若当前考察节点非空，输出该节点的值
                System.out.print(node.val + "");
                //并把该节点元素压入栈顶暂存，以方便之后找到右子树
                treeNodeStack.push(node);
                //将此节点的左子树作为新的考察节点
                node = node.left;
            }
            //直到左子树为空，再开始考虑右子树
            //若栈已空，无需再考虑
            if (!treeNodeStack.isEmpty()) {
                //弹出栈顶元素，将游标等于该节点的右子树
                node = treeNodeStack.pop();
                node = node.right;
            }
        }
}

先序遍历结果：

1	递归/非递归先序遍历：1 2 4 6 7 8 3 5

二、中序遍历（Inorder Traversal)

递归中序遍历

public static void recursionInorderTraversal(TreeNode root) {
       if (root != null) {
           recursionInorderTraversal(root.left);
           System.out.print(root.val + "");
           recursionInorderTraversal(root.right);
       }
   }

非递归中序遍历

永远优先访问左子树，直到左子树节点为空时才访问根节点。

与非递归先序遍历类似，只不过考察到当前节点时，并不直接输出该节点。而是当左节点为空时，从栈中弹出再输出。

//非递归中序遍历
  public static void InorderTraversal(TreeNode root) {
      Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
      TreeNode node = root;
      while (node != null || !treeNodeStack.isEmpty()) {
          while (node != null) {
              treeNodeStack.push(node);
              node = node.left;
          }
          //当考察节点为空时，弹出栈顶元素，再进行输出
          if (!treeNodeStack.isEmpty()) {
              node = treeNodeStack.pop();
              System.out.print(node);
              node = node.right;
          }
      }
  }

中序遍历结果

1	递归/非递归中序遍历结果：4 7 6 8 2 1 3 5

三、后序遍历(Postorder Traversal)

递归后序遍历

//递归后序遍历
public static void recursionPostorderTraversal(TreeNode root) {
    if (root != null) {
        recursionPostorderTraversal(root.left);
        recursionPostorderTraversal(root.right);
        System.out.print(root.val + "");
    }
}

非递归后序遍历

后序遍历的非递归实现是三种遍历方式中最难的一种，要保证根节点在其左右子树都访问之后才能访问，并且左子树在右子树之前访问才能访问根节点。

设置一个lastVisit游标，若lastVisit等于当前考察节点的右子树，说明该节点的左右子树都已经遍历完成，则可以输出当前节点。

并把lastVisit节点更新为此输出的当前节点。将当前游标节点node设置为空，下一轮就可以不再重复while循环而直接查看栈顶元素，再进行if判断。

若是当前考察节点的右子树不为空且不等于lastVisit，继续遍历右子树节点。

//非递归后序遍历
 public static void postorderTraversal(TreeNode root) {
     Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
     TreeNode node = root;
     //设置一个游标null
     TreeNode lastVisit = root;
     while (node != null || !treeNodeStack.isEmpty()) {
         while (node != null) {
             treeNodeStack.push(node);
             node = node.left;
         }
         //当左子树节点为空，跳出循环
         //查看当前栈顶元素
         node = treeNodeStack.peek();
         //若其右子树也为空，或者右子树已经访问
         //则可以直接输出该节点的值
         if (node.right == null || node.right == lastVisit) {
             System.out.print(node.val + "");
             //弹出栈顶元素
             treeNodeStack.pop();
             lastVisit = node;
             //将当前游标节点node设置为空
             node = null;
         } else {
             //否则，继续遍历右子树
             node = node.right;
         }
     }
 }

后序遍历结果

1	递归/非递归后序遍历结果：7 8 6 4 2 5 3 1

参考：

二叉树遍历 (先序、中序、后序)