二叉树的四种遍历方式（前序遍历、中序遍历、后序遍历、测层序遍历）_二叉树遍历前序中序后序

一、二叉树的遍历

• 遍历是数据结构中的常见的操作，把所有元素都访问一遍。

• 线性数据结构的遍历比较简单
  ①、正序遍历
  ②、逆序遍历

• 根据节点访问顺序的不同，二叉树的常见遍历方式用四种
  ①、前序遍历（Preorder Traversal）
  ②、中序遍历（Inorder Traversal）
  ③、后序遍历（Postorder Traversal）
  ④、层序遍历（Level Order Traversal）
  

（一）1、前序遍历（Preorder Traversal）

• 访问顺序：根节点、前序遍历左子树、前序遍历右子树
• 7、4、2、1、3、5、9、8、11、10、12
  
  前序遍历的方法为：

public void preorderTraversal() {
	preorderTraversal(root);
}

public void preorderTraversal(Node<E> node) {
	if(node == null) return;
	
	System.out.println(node.element);
	preorderTraversal(node.left);
	preorderTraversal(node.right);
}
1
2
3
4
5
6
7
8
9
10
11

（一）2、前序遍历 - 非递归

利用栈实现

(1)、设置node = root

(2)、循环执行以下操作

• 如果node != null
  ①.对node进行访问
  ②.对node.right入栈
  ③.设置node = node.left
• 如果node == null
  ①.如果栈为空,结束遍历
  ②.如果栈不为空,弹出栈顶元素并赋值给node

（二）1、中序遍历（Inorder Traversal）

• 访问顺序：中序遍历左子树、根节点、中序遍历右子树
• 1、2、3、4、5、7、8、9、10、11、12

/* 中序遍历 */
public void inorderTraversal() {
	inorderTraversal(root);
}

private void inorderTraversal(Node<E> node) {
	if(node == null) return;
	
	inorderTraversal(node.left);
	System.out.println(node.element);
	inorderTraversal(node.right);
}
1
2
3
4
5
6
7
8
9
10
11
12

• 如果是访问顺序是下面这样呢？
  中序遍历右子树、根节点、中序遍历左子树
  12、11、10、9、8、7、5、4、3、2、1

/* 中序遍历 */
public void inorderTraversal() {
	inorderTraversal(root);
}

private void inorderTraversal(Node<E> node) {
	if(node == null) return;
	
	inorderTraversal(node.right);
	System.out.println(node.element);
	inorderTraversal(node.left);
}
1
2
3
4
5
6
7
8
9
10
11
12

• 二叉搜索树的中序遍历结果是升序或者降序的

（二）2、中序遍历 - 非递归

利用栈实现

(1)、设置node = root

(2)、循环执行以下操作

• 如果node != null
  ①.对node入栈
  ②.设置node = node.left
• 如果node == null
  ①、如果栈为空，结束遍历。
  ②、如果栈不为空，弹出栈顶元素并赋值给node
• 对node进行访问
• 设置node = node.rigth

（三）1、后序遍历（Postorder Traversal）

• 访问顺序：后序遍历左子树、后序遍历右子树、根节点
• 1、3、2、5、4、8、10、12、11、9、7
  

/* 后序遍历 */
public void postorderTraversal() {
	postorderTraversal(root);
}

private void postorderTraversal(Node<E> node) {
	if(node == null) return;
	
	postorderTraversal(node.left);
	postorderTraversal(node.right);
	System.out.println(node.element);
}
1
2
3
4
5
6
7
8
9
10
11
12

（三）2、后序遍历 - 非递归

利用栈实现

(1)、将root入栈

(2)、循环执行以下操作，直到栈为空

• 如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点
  ①.弹出栈顶节点，进行访问
• 否则
  ①、将栈顶节点right、left按顺序入栈。

（四）层序遍历（Level Order Traversal）

• 访问顺序：从上到下，从左到右依次访问每一个节点
• 7、4、9、2、5、8、11、1、3、10、12
• 实现思路：使用队列
  ①、将根节点入队
  ②、循环执行以下操作，直到队列为空
  Ⅰ将队头节点A出队，进行访问。
  Ⅱ将A的左子节点入队。
  Ⅲ将A的右子节点入队。

/* 层序遍历 */
public void levelOrderTraversal() {
	if (root == null) return;
	
	Queue<Node<E>> queue = new LinkedList<>();
	queue.offer(root);
	
	while (!queue.isEmpty()) {
		Node<E> node =  queue.poll();
		System.out.println(node.element);
		
		if (node.left != null) {
			queue.offer(node.left);
		}
		if (node.right != null) {
			queue.offer(node.right);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

打印二叉树工具

• 工具：https://github.com/CoderMJLee/BinaryTrees
• 使用步骤：
  ①、调用BinaryTreeInfo接口
  ②、调用打印APIBinaryTrees.println(bst);

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

import com.mj.printer.BinaryTreeInfo;

public class BinarySearchTree<E> implements BinaryTreeInfo {
	private int size;
	private Node<E> root;
	private Comparator<E> comparator;
	
	public BinarySearchTree() {
		this(null);
	}
	
	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	/* 元素的数量 */
	public int size() {
		return size;
	}
	/* 是否为空 */
	public boolean isEmpty() {
		return size==0;
	}
	/*  清空所有的元素  */
	public void clear() {
		
	}
	/*  添加元素 */
	public void add(E element) {
		elementNotNullCheck(element);
		
		if(root == null) {
			//添加第一个节点
			root = new Node<>(element, null);
			size++;
			return;
		}
		
		//添加的不是第一个节点
		//找到父节点
		Node<E> node = root;
		Node<E> parent = null;
		int cmp = 0;
		while (node != null) {
			cmp = compare(element, node.element);
			
			parent = node;
			
			if (cmp > 0) {
				node = node.right;
			}else if (cmp < 0) {
				node = node.left;
			}else {//相等
				node.element = element;
				return;
			}
		}
		
		//看看插入到父节点的哪个位置
		Node<E> newNode = new Node<>(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		}else {
			parent.left = newNode;
		}
		size++;
		
		
	}
	/* 删除元素 */
	public void remove(E element) {
		
	}
	/* 是否包含某元素 */
	public boolean contains(E element) {
		return false;
	}
	
	//前序遍历
	public void preorder(Visitor<E> visitor) {
		if(visitor == null) return;
		preorder(root,visitor);
	}
	
	private void preorder(Node<E> node, Visitor<E> visitor) {
		if (node == null) return;
		
		visitor.visit(node.element);//先访问自己的元素
		preorder(node.left,visitor);//前序遍历自己的左子树
		preorder(node.right,visitor);//前序遍历自己的右子树
	}
	
	//中序遍历
	public void inorder(Visitor<E> visitor) {
		if(visitor == null) return;
		inorder(root,visitor);
	}
	
	private void inorder(Node<E> node, Visitor<E> visitor) {
		if (node == null) return;
		
		inorder(node.left,visitor);//中序遍历自己的左子树
		visitor.visit(node.element);//先访问自己的元素
		inorder(node.right,visitor);//中序遍历自己的右子树
	}
	
	//后序遍历
	public void postorder(Visitor<E> visitor) {
		if(visitor == null) return;
		postorder(root,visitor);
	}
	
	private void postorder(Node<E> node, Visitor<E> visitor) {
		if (node == null) return;
		
		postorder(node.left,visitor);//后序遍历自己的左子树
		postorder(node.right,visitor);//后序遍历自己的右子树
		visitor.visit(node.element);//先访问自己的元素
	}
	
	public void levelOrder(Visitor<E> visitor) {
		if (root == null || visitor == null) return;
		
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		
		while (!queue.isEmpty()) {
			Node<E> node =  queue.poll();
			visitor.visit(node.element);
			
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
	}
	
	/**
	 * @return 返回值等于0,代表e1和e2相等;
	 * 返回值大于0,代表e1大于e2;
	 * 返回值小于0,代表e1小于e2;
	 */
	@SuppressWarnings("unchecked")
	public int compare(E e1,E e2) {
		if (comparator != null) {
			return comparator.compare(e1, e2);
		}
		return ((Comparable<E>)e1).compareTo(e2);
	}
	
	
	//由于二叉搜索树不能为空，所以要做一个检测
	private void elementNotNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element must not be null!!");
		}
	}
	
	public static interface Visitor<E>{
		boolean visit(E element);
	}
	
	private static class Node<E>{
		E element;
		Node<E> left;
		Node<E> right;
		@SuppressWarnings("unused")
		Node<E> parent;
		
		public Node(E element,Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
	}

	@Override
	public Object root() {
		return root;
	}

	@Override
	public Object left(Object node) {
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		Node<E> myNode = (Node<E>) node;
		String parentString = "null";
		if (myNode.parent != null) {
			parentString = myNode.parent.element.toString();
		}
		return myNode.element+"_p("+parentString+")";
	}
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

测试打印二叉树：

import java.util.Comparator;
import com.mj.BinarySearchTree.Visitor;
import com.mj.file.Files;
import com.mj.printer.BinaryTrees;

public class Main {
	static void test9() {
		Integer date[] = new Integer[] {
				7,4,9,2,1
		};
		
		BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
		for (int i = 0; i < date.length; i++) {
			bst.add(date[i]);
		}
		BinaryTrees.println(bst);
		
		System.out.print("前序遍历：");
		bst.preorder(new Visitor<Integer>() {
			public void visit(Integer integer) {
				System.out.print(integer+" ");
			}
		});
		System.out.println();
		System.out.print("中序遍历：");
		bst.inorder(new Visitor<Integer>() {
			public void visit(Integer integer) {
				System.out.print(integer+" ");
			}
		});
		System.out.println();
		System.out.print("后序遍历：");
		bst.postorder(new Visitor<Integer>() {
			public void visit(Integer integer) {
				System.out.print(integer+" ");
			}
		});
		System.out.println();
		System.out.print("层序遍历：");
		bst.levelOrder(new Visitor<Integer>() {
			public void visit(Integer integer) {
				System.out.print(integer+" ");
			}
		});
	}
	
	public static void main(String[] args) {
		test9();
	}
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

运行结果：

             ┌─7_p(null)─┐
             │           │
        ┌─4_p(7)       9_p(7)
        │
   ┌─2_p(4)
   │
1_p(2)
前序遍历：7 4 2 1 9 
中序遍历：1 2 4 7 9 
后序遍历：1 2 4 9 7 
层序遍历：7 4 9 2 1 
1
2
3
4
5
6
7
8
9
10
11

上述的遍历只是从头遍历到尾部，一直遍历下去，无法停止【即上面有多少个元素就遍历多少次】。但是不可以随时终止这个遍历，如何实现随时终止遍历的操作呢？

//前序遍历
public void preorder(Visitor<E> visitor) {
	if(visitor == null) return;
	preorder(root,visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
	if (node == null || visitor.stop) return;
	
	visitor.stop = visitor.visit(node.element);//先访问自己的元素
	preorder(node.left,visitor);//前序遍历自己的左子树
	preorder(node.right,visitor);//前序遍历自己的右子树
}

//中序遍历
public void inorder(Visitor<E> visitor) {
	if(visitor == null) return;
	inorder(root,visitor);
}

private void inorder(Node<E> node, Visitor<E> visitor) {
	if (node == null || visitor.stop) return;
	
	inorder(node.left,visitor);//中序遍历自己的左子树
	if(visitor.stop) return;
	visitor.stop = visitor.visit(node.element);//先访问自己的元素
	inorder(node.right,visitor);//中序遍历自己的右子树
}

//后序遍历
public void postorder(Visitor<E> visitor) {
	if(visitor == null) return;
	postorder(root,visitor);
}

private void postorder(Node<E> node, Visitor<E> visitor) {
	if (node == null || visitor.stop) return;
	
	postorder(node.left,visitor);//后序遍历自己的左子树
	postorder(node.right,visitor);//后序遍历自己的右子树
	
	if(visitor.stop) return;
	visitor.stop = visitor.visit(node.element);//先访问自己的元素
}

//层序遍历
public void levelOrder(Visitor<E> visitor) {
	if (root == null || visitor == null) return;
	
	Queue<Node<E>> queue = new LinkedList<>();
	queue.offer(root);
	
	while (!queue.isEmpty()) {
		Node<E> node =  queue.poll();
		if(visitor.visit(node.element)) return;
		
		if (node.left != null) {
			queue.offer(node.left);
		}
		if (node.right != null) {
			queue.offer(node.right);
		}
		
	}
}

public static abstract class Visitor<E>{
	boolean stop;
	/**
	 * @return 如果返回true，就代表停止遍历
	 */
	abstract boolean visit(E element);
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import java.util.Comparator;
import com.mj.BinarySearchTree.Visitor;
import com.mj.file.Files;
import com.mj.printer.BinaryTrees;

public class Main {
	static void test9() {
		Integer date[] = new Integer[] {
				7,4,9,2,1
		};
		
		BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
		for (int i = 0; i < date.length; i++) {
			bst.add(date[i]);
		}
		BinaryTrees.println(bst);
		
		System.out.print("前序遍历：");
		bst.preorder(new Visitor<Integer>() {
			public boolean visit(Integer integer) {
				System.out.print(integer+" ");
				return integer == 2 ? true : false;
			}
		});
		System.out.println();
		System.out.print("中序遍历：");
		bst.inorder(new Visitor<Integer>() {
			public boolean visit(Integer integer) {
				System.out.print(integer+" ");
				return integer == 4 ? true : false;
			}
		});
		System.out.println();
		System.out.print("后序遍历：");
		bst.postorder(new Visitor<Integer>() {
			public boolean visit(Integer integer) {
				System.out.print(integer+" ");
				return integer == 4 ? true : false;
			}
		});
		System.out.println();
		System.out.print("层序遍历：");
		bst.levelOrder(new Visitor<Integer>() {
			public boolean visit(Integer integer) {
				System.out.print(integer+" ");
				return integer == 9 ? true : false;
			}
		});
	}
	
	public static void main(String[] args) {
		test9();
	}
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

             ┌─7_p(null)─┐
             │           │
        ┌─4_p(7)       9_p(7)
        │
   ┌─2_p(4)
   │
1_p(2)
前序遍历：7 4 2 
中序遍历：1 2 4 
后序遍历：1 2 4 
层序遍历：7 4 9 
1
2
3
4
5
6
7
8
9
10
11