二叉树的遍历（代码+图文详解）

二叉树的遍历

• 遍历实际上是指按照某个规则对二叉树中的每个节点进行操作，并且每个节点只操作一次（打印出二叉树的每一个节点内容或每个节点值域+1都算遍历）
• 遍历方式有三种，分别是：

	前序遍历	中序遍历	后序遍历
遍历方式	根-->左-->右	左-->根-->右	左-->右-->根
共同点	都是先遍历左子树，再遍历右子树
不同点	根节点的遍历次序不同

递归版遍历

• 前序遍历
  

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

• 中序遍历
  

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

• 后序遍历
  

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

非递归版遍历！！重要

一般递归转非递归有两种方式：循环和借用栈

根据递归遍历二叉树发现后递归的先退出，这样递归调用的返回的特性和栈的特性一样，所以可以利用栈来实现二叉树的非递归遍历

层序遍历的实现：

在写前序遍历之前可以先了解下层序遍历
二叉树的层序遍历实际上就是广度优先遍历，一层处理完后在处理下一层

 // 层序遍历 public void LevelOrder(){ if(null == root){ return; } Queue<BTNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()){ BTNode cur = q.poll(); System.out.print(cur.val); // 如果cur有左子树，让左子树入队列 if(null != cur.left){ q.offer(cur.left); } // 如果cur有右子树，让右子树入队列 if(null != cur.right){ q.offer(cur.right); } } System.out.println(); } 

前序遍历

前序非递归遍历第一种方式：

 //前序非递归遍历 public void preOrder1(TreeNode root){ if (root == null){ return; } Stack<TreeNode> s = new Stack<>(); s.push(root); //栈不为空 while(!s.empty()){ TreeNode cur = s.pop(); System.out.print(cur.val+" "); //因为栈是先进后出，所以如果想要先左后右的话就要先保存右子树再保存左子树 //判断当前节点是否有右子树,如果有右子树则让他入栈 if(null != cur.right){ s.push(cur.right); } //判断当前节点是否有左子树,如果有左子树则让他入栈 if(null != cur.left){ s.push(cur.left); } } } 

前序非递归遍历第二种方式：

 // 前序非递归第二种方式 public static void preOrder2(TreeNode root){ // 先判断树是否为空 if(root == null){ return; } Stack<TreeNode> s = new Stack<>(); s.push(root); if(!s.empty()){ TreeNode cur = s.pop(); if (cur != null){ System.out.println(cur.val + " "); // 顺着cur的左侧路径一路向下遍历，并保存途径的右子树 if(cur.right != null){ s.push(cur.right); } cur = cur.left; } } System.out.println(); } 

中序遍历

 public static void inOrder1(TreeNode root){ if(null == root){ return; } Stack<TreeNode> s = new Stack<>(); TreeNode cur = root; //中序遍历先遍历树的左子树 //所以首先要做的是从root开始找到最左节点，并保存路径上经过的节点 while(null != cur || !s.empty()){ while(null != cur){ s.push(cur); cur = cur.left; } //退出循环说明cur==null，此时栈顶元素就是二叉树最左侧节点 cur = s.pop(); System.out.print(cur.val+" "); //以cur为根的左子树和根遍历完了，还剩右子树 cur = cur.right; } System.out.println(); } 

后序遍历

 public static void lastOrder1(TreeNode root){ //还是先判断root是否为空 if(null == root){ return; } Stack<TreeNode> s = new Stack<>(); TreeNode cur = root; TreeNode prev = null; while(null != cur || !s.empty()){ // 找到最左结点，并且保存途径的所有结点 while(null != cur){ s.push(cur); cur = cur.left; } // cur为空说明左子树已经遍历完毕，获取右子树 // 获取右子树又需要获取到右子树的根节点，也就是当前栈顶元素 TreeNode top = s.peek(); // top的右子树为空，或右子树之前被遍历过，直接遍历根节点 if(top.right == null || prev == top.right){ System.out.print(top.val + " "); prev = s.pop(); }else { // 右子树没被遍历过 cur = top.right; } } System.out.println(); } 

本文地址：https://blog.csdn.net/qq_43360037/article/details/105913778