介绍
二叉树的四种遍历方式：
- 二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。
四种遍历方式分别为：先序遍历、中序遍历、后序遍历、层序遍历。
![]()
遍历之前，我们首先介绍一下，如何创建一个二叉树，在这里用的是先建左树在建右树的方法，
首先要声明结点TreeNode类，代码如下：
1
2
3
4
5
6
7
8
9
10
| public class TreeNode {
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(int data){
this.data = data;
}
}
|
再来创建一棵二叉树：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static TreeNode createBinaryTree(LinkedList<Integer> list){
TreeNode node = null;
if(list == null || list.isEmpty()){
return null;
}
Integer data = list.removeFirst();
if(data!=null){
node = new TreeNode(data);
node.leftChild = createBinaryTree(list);
node.rightChild = createBinaryTree(list);
}
return node;
}
|
实现
接下来按照上面列的顺序一一讲解，
前序遍历
首先来看前序遍历，所谓的前序遍历就是先访问根节点，再访问左节点，最后访问右节点，
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void preOrderTraveral(TreeNode node){
if(node == null){
return;
}
System.out.print(node.data+" ");
preOrderTraveral(node.leftChild);
preOrderTraveral(node.rightChild);
}
|
中序遍历
再者就是中序遍历，所谓的中序遍历就是先访问左节点，再访问根节点，最后访问右节点，
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void inOrderTraveral(TreeNode node){
if(node == null){
return;
}
inOrderTraveral(node.leftChild);
System.out.print(node.data+" ");
inOrderTraveral(node.rightChild);
}
|
后序遍历
最后就是后序遍历，所谓的后序遍历就是先访问左节点，再访问右节点，最后访问根节点。
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void postOrderTraveral(TreeNode node){
if(node == null){
return;
}
postOrderTraveral(node.leftChild);
postOrderTraveral(node.rightChild);
System.out.print(node.data+" ");
}
|
非递归方案
讲完上面三种递归的方法，下面再给大家讲讲非递归是如何实现前中后序遍历的
还是一样，先看非递归前序遍历
- 首先申请一个新的栈，记为stack；
- 声明一个结点treeNode，让其指向node结点；
- 如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的右结点，
- 重复步骤3，直到treenode为空；
- 然后出栈，让treeNode指向treeNode的右孩子
- 重复步骤3，直到stack为空.
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void preOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
System.out.print(treeNode.data+" ");
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
|
中序遍历非递归，在此不过多叙述具体步骤了，
具体过程：
- 申请一个新栈，记为stack，申请一个变量cur，初始时令treeNode为头节点；
- 先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；
- 不断重复步骤2，直到发现cur为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；
- 当stack为空并且cur为空时结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void inOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
System.out.print(treeNode.data+" ");
treeNode = treeNode.rightChild;
}
}
}
|
后序遍历非递归实现，后序遍历这里较前两者实现复杂一点，我们需要一个标记位来记忆我们此时节点上一个节点，具体看代码注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public static void postOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
TreeNode lastVisit = null;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
System.out.print(treeNode.data + " ");
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.rightChild;
}
}
}
}
|
最后再给大家介绍一下层序遍历
具体步骤如下：
- 首先申请一个新的队列，记为queue；
- 将头结点head压入queue中；
- 每次从queue中出队，记为node，然后打印node值，如果node左孩子不为空，则将左孩子入队；如果node的右孩子不为空，则将右孩子入队；
- 重复步骤3，直到queue为空。
实现代码如下：
1
2
3
4
5
6
7
8
9
10
| public static void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.data+" ");
if(root.leftChild!=null) queue.add(root.leftChild);
if(root.rightChild!=null) queue.add(root.rightChild);
}
}
|
