二叉树的遍历（traversing binary tree）
是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。
-
前序遍历（根 左 右）
先访问根结点，然后前序遍历左子树，再前序遍历右子树
-
中序遍历（左 根 右）
中序遍历根结点的左子树，然后访问根结点，最后遍历右子树
-
后序遍历（左 右 根）
从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点
-
层级遍历（从上到下 从左到右）
从根结点从上往下从左往右依次遍历
据上图，得根据不同的遍历方式，得到的结果不同：
前序遍历： a b d c e f g
中序遍历： d b a f e g c
后序遍历： d b f g e c a
层级遍历： a b c d e f g
二叉树遍历的实现分为两种：
- 一种是使用递归实现；
- 另一种是借助 Stack 和 Queue（栈和队列）来实现
下面使用递归的方式来实现。
0. 在遍历之前，先来创建一个二叉树（先建左树再建右树
public class TreeNode {
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(int data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
}
1. 前序遍历
/**
* 先序遍历（根左右）
*
* @param treeNode
*/
public static void preOrder(TreeNode treeNode) {
if (treeNode == null) {
return;
}
System.out.println(treeNode.data);
preOrder(treeNode.leftChild);
preOrder(treeNode.rightChild);
}
2. 中序遍历
/**
* 中序遍历（左根右）
*
* @param treeNode
*/
public static void midOrder(TreeNode treeNode) {
if (treeNode == null) {
return;
}
midOrder(treeNode.leftChild);
System.out.println(treeNode.data);
midOrder(treeNode.rightChild);
}
3. 后序遍历
/**
* 后序遍历（左右根）
*
* @param treeNode
*/
public static void lastOrder(TreeNode treeNode) {
if (treeNode == null) {
return;
}
lastOrder(treeNode.leftChild);
lastOrder(treeNode.rightChild);
System.out.println(treeNode.data);
}
4. 层级遍历
/**
* 层级遍历（左右根）
*
* @param treeNode
*/
public static void floorOrder(TreeNode treeNode) {
if (treeNode == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(treeNode);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
System.out.println(temp.data);
if (temp.leftChild != null)
queue.add(temp.leftChild);
if (temp.rightChild != null)
queue.add(temp.rightChild);
}
}
测试
public static void main(String[] args) {
TreeNode tree = new TreeNode(3);
TreeNode left = new TreeNode(2);
left.leftChild = new TreeNode(1);
left.rightChild = new TreeNode(4);
TreeNode right = new TreeNode(5);
tree.leftChild = left;
tree.rightChild = right;
System.out.println("=== 先序遍历 ===");
preOrder(tree);
System.out.println("=== 中序遍历 ===");
midOrder(tree);
System.out.println("=== 后序遍历 ===");
lastOrder(tree);
}
=== 先序遍历 ===
3
2
1
4
5
=== 中序遍历 ===
1
2
4
3
5
=== 后序遍历 ===
1
4
2
5
3
=== 层级遍历 ===
3
2
5
1
4
上面创建的二叉树，用图表示为：
