二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历java二叉树的遍历算法，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此採用递归的方法去实现树的三种遍历不仅easy理解并且代码非常简洁，而对于广度遍历来说，须要其他数据结构的支撑。比方堆了。
四种基本的遍历思想为：
前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
层次遍历：仅仅需按层次遍历就可以
比如。求以下二叉树的各种遍历
1
/ \
2 3
/ \ /
4 5 6
/ \
7 8
前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 6 3
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8
二叉树的代码
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
一、前序遍历
1）依据上文提到的遍历思路：根结点 —> 左子树 —> 右子树，非常easy写出递归版本号：
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.val + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
2）如今讨论非递归的版本号：
依据前序遍历的顺序，优先訪问根结点。然后在訪问左子树和右子树。所以。对于随意结点node。第一部分即直接訪问之，之后在推断左子树是否为空，不为空时即反复上面的步骤，直到其为空。若为空。则须要訪问右子树。注意。在訪问过左孩子之后。须要反过来訪问其右孩子。所以，须要栈这样的数据结构的支持。对于随意一个结点node，详细过程例如以下：
a)訪问之，并把结点node入栈。当前结点置为左孩子；
b)推断结点node是否为空，若为空。则取出栈顶结点并出栈，将右孩子置为当前结点；否则反复a)步直到当前结点为空或者栈为空（能够发现栈中的结点就是为了訪问右孩子才存储的）
代码例如以下：
//先序遍历的非递归的写法，反着它的顺序写
// 1.先放中节点
// 2.有右节点放右节点
// 3.有左节点放左节点
public static void preOrderUnRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print("pre-order: ");
Stack stack = new Stack();
stack.add(head);
while (!stack.isEmpty()) {
TreeNode pop = stack.pop();
System.out.print(pop.val + " ");
if (pop.right != null) {
stack.add(pop.right);
}
if (pop.left != null) {
stack.add(pop.left);
}
}
}
二、中序遍历
1)依据上文提到的遍历思路：左子树 —> 根结点 —> 右子树，非常easy写出递归版本号：
public static void inOrderRecur(TreeNode head) {
if (head == null) {
return;
}
inOrderRecur(head.left);
System.out.print(head.val + " ");
inOrderRecur(head.right);
}
2）非递归实现，有了上面前序的解释java二叉树的遍历算法，中序也就比較简单了。同样的道理。仅仅只是訪问的顺序移到出栈时。代码例如以下：
//中序遍历的非递归的写法，
// 1.左节点不为null则压入左节点
// 2.左节点为null时，pop并打印，左节点
// 3.在往右，右节点为null时，pop并打印
// 4.右节点不为null时，压入右节点
//还是背下来吧
public static void inOrderUnRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print("in-order: ");
Stack stack = new Stack();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.add(head);
head = head.left;
} else {
head = stack.pop();
System.out.print(head.val + " ");
head = head.right;
}
}
}
三、后序遍历
1）依据上文提到的遍历思路：左子树 —> 右子树 —> 根结点。非常easy写出递归版本号：
public static void posOrderRecur(TreeNode head) {
if (head == null) {
return;
}
posOrderRecur(head.left);
posOrderRecur(head.right);
System.out.print(head.val + " ");
}
2）非递归实现
//和前序遍历一样的只不过是使用了两个栈
//在前序遍历的时候将 中 右 左 节点压栈
//在原来是打印的地方不打印，将本该打印的节点压到第二个栈中
//这样第二个栈的出栈顺序就是 右 左 中了
public static void posOrderUnRecur1(TreeNode head) {
if (head == null) {
return;
}
System.out.print("pos-order: ");
Stack stack = new Stack();
Stack stack2 = new Stack();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
//在这里不打印，这里我们放到第二个栈中去
stack2.add(head);
if (head.left != null) {
stack.add(head.left);
}
if (head.right != null) {
stack.add(head.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().val + " ");
}
}
四、层次遍历
层次遍历的代码比較简单。仅仅须要一个队列就可以。先在队列中增加根结点。之后对于随意一个结点来说。在其出队列的时候java二叉树的遍历算法-二叉树遍历（前序、中序、后序、层次、深度优先）递归和非递归 java实现，訪问之。同一时候假设左孩子和右孩子有不为空的。入队列。代码例如以下：
//层次遍历
public ArrayList PrintFromTopToBottom(TreeNode root) {
ArrayList result = new ArrayList();
if (root == null) {
return result;
}
LinkedList queue = new LinkedList();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode poll = queue.poll();
result.add(poll.val);
if (poll.left != null) {
queue.add(poll.left);
}
if (poll.left != null) {
queue.add(poll.right);
}
}
return result;
}
文章来源:https://blog.csdn.net/qq_37859539/article/details/81462171