二叉树最常见的遍历方式有三种，前序，中序和后序
一. 前序遍历
前序遍历就是按照根节点，左子树，右子树的顺序来遍历二叉树，在遍历左右子树的时候依然是采用前序遍历的方式
前序遍历的结果为：ABDECF
生成一棵这样的二叉树
//构建二叉树类 class TreeNode { char c; TreeNode left; TreeNode right; TreeNode(char c) { this.c = c; } }
TreeNode root3 = new TreeNode(‘A‘); root3.left = new TreeNode(‘B‘); root3.right = new TreeNode(‘C‘); root3.left.left = new TreeNode(‘D‘); root3.left.right = new TreeNode(‘E‘); root3.right.right = new TreeNode(‘F‘);
前序遍历递归代码
//递归方法前序遍历二叉树 public static void preOrderRe(TreeNode node) { if(node == null) return; System.out.print(node.c + " "); preOrderRe(node.left); preOrderRe(node.right); }
前序遍历非递归栈代码
//非递归栈实现前序遍历 public static void preOrder(TreeNode node){ if(node == null){ return; } Stack<TreeNode> stack = new Stack<>(); stack.push(node); while(!stack.isEmpty()){ //出栈和进栈 TreeNode n = stack.pop();//弹出根结点 //压入子结点 System.out.print(n.val + " "); if(n.right!=null){ stack.push(n.right); } if(n.left!=null){ stack.push(n.left); } } }
运行结果：
二. 中序遍历
中序遍历就是按照左子树，根节点，右子树的顺序来遍历二叉树，在遍历左右子树的时候依然是采用中序遍历的方式
以上图的二叉树为例子，中序遍历的结果为：DBEACF
//递归方法中序遍历二叉树 public static void midOrderRe(TreeNode node) { if (node == null) return; midOrderRe(node.left); System.out.print(node.c + " "); midOrderRe(node.right); }
//非递归栈实现中序遍历 public static void midOrder(TreeNode node){ Stack<TreeNode> stack = new Stack<>(); while (node != null || !stack.isEmpty()){ while (node != null){ stack.push(node); node = node.left; } if(!stack.isEmpty()){ node = stack.pop(); System.out.println(node.c + " "); node = node.right; } } }
运行结果：
三. 后序遍历
中序遍历就是按照左子树，右子树，根节点的顺序来遍历二叉树，在遍历左右子树的时候依然是采用后序遍历的方式
以上图的二叉树为例子，中序遍历的结果为：DEBFAC
//递归方法后序遍历二叉树 public static void postOrderRe(TreeNode node) { if (node == null) return; postOrderRe(node.left); postOrderRe(node.right); System.out.print(node.c + " "); }
运行结果：
四. 层序遍历
层序遍历二叉树就是从上到下，从左到右，一层一层地遍历二叉树
以上图的二叉树为例子，层序遍历的结果为：ABCDEF
层序遍历可以通过队列来实现
//层序遍历，使用队列，从上到下，从左到右 public static void levelOrder(TreeNode node){ Queue<TreeNode> queue = new ArrayDeque<>(); queue.offer(node); while (!queue.isEmpty()){ int size = queue.size(); for (int i=0; i<size; i++){ node = queue.poll(); System.out.print(node.c + " "); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } System.out.println(); } }
运行结果：