目录
二叉树是一种重要的数据结构，其遍历方式分为：深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即就是层次遍历。如下图：
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);
}
}
}?
?