二叉树的五种遍历方式

二叉树的五种遍历方式

目录

1、前序遍历

（1）递归实现前序遍历

（2）非递归实现前序遍历

 2、中序遍历

（1）递归实现中序遍历

（2）非递归实现中序遍历

 3、后序遍历

（1）递归实现后序遍历

（2）非递归实现后序遍历

4、层序遍历

5、之字形遍历

---

二叉树是一种重要的数据结构，其遍历方式分为：深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即就是层次遍历。如下图：

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

1、前序遍历

遍历顺序：根节点---左子树---右子树

如上图，遍历结果应该为：12457836

（1）递归实现前序遍历

    /*** 递归实现前序遍历* @param treeNode  树的根节点*/public static void preOrder1(TreeNode treeNode){// 若根节点为空，直接返回if(treeNode == null){return;}//打印根节点System.out.print(treeNode.val + "\t");// 遍历根节点的左子树preOrder1(treeNode.left);// 遍历根节点的右子树preOrder1(treeNode.right);}

（2）非递归实现前序遍历

非递归实现可以通过辅助栈或者辅助队列实现。以下代码为辅助栈的实现方式：

    /*** 非递归实现前序遍历* @param treeNode  根节点*/public static void preOrder2(TreeNode treeNode){// 如果根节点为空，直接返回。if(treeNode == null){return;}// 辅助栈Stack<TreeNode> stack = new Stack<>();// 根节点入栈stack.push(treeNode);// 当栈不为空while(!stack.isEmpty()){//取出栈顶元素TreeNode node = stack.pop();//打印根节点System.out.print(node.val + "\t");// 如果使用的是辅助栈，则先将根节点的右子节点入栈；如果是辅助队列，则先将根节点的左子节点入队列。因为栈是先进后出，队列是先进入=先出if(node.right != null){stack.push(node.right);}// 根节点的右子节点入栈if(node.left != null){stack.push(node.left);}}}

 2、中序遍历

遍历顺序：左子树---根节点---右子树

如上图，遍历结果应该为：42758136

（1）递归实现中序遍历

    /*** 递归实现中序遍历* @param treeNode  树的根节点*/public static void inOrder1(TreeNode treeNode){// 若根节点为空，直接返回if(treeNode == null){return;}// 遍历根节点的左子树inOrder1(treeNode.left);//打印根节点System.out.print(treeNode.val + "\t");// 遍历根节点的右子树inOrder1(treeNode.right);}

（2）非递归实现中序遍历

    /*** 非递归实现中序遍历* @param treeNode  根节点*/public static void inOrder2(TreeNode treeNode){// 如果根节点为空，直接返回。if(treeNode == null){return;}// 辅助栈Stack<TreeNode> stack = new Stack<>();// 临时指针TreeNode cur = treeNode;// 当栈不为空while(cur != null || !stack.isEmpty()){// 左节点入栈while(cur != null){stack.push(cur);cur = cur.left;}//取出栈顶元素cur = stack.pop();//打印左节点System.out.print(cur.val + "\t");// 指向右节点cur = cur.right;}}

 3、后序遍历

遍历顺序：左子树---右子树---根节点

如上图，遍历结果应该为：47852631

（1）递归实现后序遍历

    /*** 递归实现后序遍历* @param treeNode  树的根节点*/public static void postOrder1(TreeNode treeNode){// 若根节点为空，直接返回if(treeNode == null){return;}// 遍历根节点的左子树postOrder1(treeNode.left);// 遍历根节点的右子树postOrder1(treeNode.right);//打印根节点System.out.print(treeNode.val + "\t");}

（2）非递归实现后序遍历

 

    /*** 非递归实现后序遍历* @param treeNode  根节点*/public static void postOrder2(TreeNode treeNode){// 如果根节点为空，直接返回。if(treeNode == null){return;}// 辅助栈Stack<TreeNode> stack = new Stack<>();// 临时指针TreeNode cur = treeNode, pre = null;// 当栈不为空while(cur != null || !stack.isEmpty()){// 左节点入栈while(cur != null){stack.push(cur);cur = cur.left;}//取出栈顶元素cur = stack.get(stack.size()-1);if(cur.right == null || pre == cur.right){stack.pop();System.out.print(cur.val + "\t");pre = cur;cur = null;}else{// 指向右节点cur = cur.right;}}}

4、层序遍历

遍历顺序：逐层遍历

如上图，遍历结果应该为：12345678。通过辅助队列，在取出节点的同时，将当前节点的左右节点分别入队。

    /*** 层序遍历* @param treeNode*/public static void levelOrder(TreeNode treeNode){//根节点为空，直接返回if(treeNode == null){return;}//辅助队列Queue<TreeNode> queue = new LinkedList<>();//根节点入队列queue.offer(treeNode);//当栈不为空while(!queue.isEmpty()){//取出队首元素TreeNode node = queue.poll();System.out.print(node.val + "\t");//将节点的左节点入队if(node.left != null){queue.offer(node.left);}//节点的右节点入队if(node.right != null){queue.offer(node.right);}}}

 

5、之字形遍历

这是牛客上的一道题。这个之字形遍历也可理解为Z字形遍历，以上树为例，其遍历结果为：1，3，2，4，5，6，8，7。本质还是二叉树的层序遍历，只不过在便利的时候，要将偶数层的节点逆序。

代码：

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public ArrayList<ArrayList<Integer> > Print(TreeNode root) {//存储结果ArrayList<ArrayList<Integer>> result = new ArrayList<>();//如果根节点为空，则直接返回if(root == null){return result;}//辅助队列Queue<TreeNode> queue = new LinkedList<>();//根节点入队queue.offer(root);//是否转向boolean flag = false;while(!queue.isEmpty()){//获取队列长度int size = queue.size();//存储每一层的遍历结果ArrayList<Integer> list = new ArrayList<>();for(int i=0; i < size; i++){//取出队列元素TreeNode node = queue.poll();if(node == null){continue;}if(!flag){list.add(node.val);}else{list.add(0, node.val);}//左右节点各入队queue.offer(node.left);queue.offer(node.right);}//如果有值，存入结果集if(list.size() > 0){result.add(list);}//转向flag = !flag;}return result;}}