二叉树的前、中、后、层序遍历
二叉树的遍历
遍历：把二叉树中所有节点都访问一遍且只访问一次。
二叉树有以下四种遍历方式：
前序遍历: 先访问父节点，再遍历左子树和右子树。
中序遍历: 先遍历左子树，再访问父节点，再遍历右子树。
后序遍历: 先遍历左子树，再遍历右子树，最后访问父节点。
层序遍历：也叫层次遍历，从根节点开始往下一层一层的遍历节点。
小结: 看访问父节点的顺序，就能确定是前序，中序还是后序遍历。
前序遍历
前序遍历的访问顺序为：父节点、前序遍历左子树、前序遍历右子树。
下面的二叉树前序遍历的结果为7、4、2、1、3、5、9、8、11、10、12。
前序遍历的代码实现：
/**
* 前序遍历
*/
public void preorder() {
preorder(root);
}
private void preorder(Node<E> node) {
if(null == node) {
return;
}
System.out.println(node.value);
if(null != node.left) {
preorder(node.left);
}
if(null != node.right) {
preorder(node.right);
}
}
前面的前序遍历只实现了对节点的打印，如果想要自定义对节点的操作以及访问到某个节点就终止遍历，怎么实现？
下面实现对前序遍历的增强：
增加遍历接口：
public static abstract class Vistor<E> {
protected boolean stop;
/**
* 遍历节点
* @param e
* @return true-停止遍历，false-继续遍历
*/
public abstract boolean visit(E e);
}
前序遍历增强方法：
/**
* 前序遍历增强
*/
public void preorder(Vistor<E> vistor) {
if (null == root || null == vistor) {
return;
}
preorder(root, vistor);
}
private void preorder(Node<E> node, Vistor<E> vistor) {
// 每次遍历前先判断标志位stop是否为true
if (null == node || vistor.stop) {
return;
}
// 将stop置为true，停止遍历
vistor.stop = vistor.visit(node.value);
if (null != node.left) {
preorder(node.left, vistor);
}
if (null != node.right) {
preorder(node.right, vistor);
}
}
中序遍历、后序遍历、层次遍历的增强与前序遍历增强类似。
中序遍历
中序遍历的访问顺序：中序遍历左子树、父节点、中序遍历右子树。
下面的二叉树中序遍历的结果为1、2、3、4、5、7、8、9、10、11、12。
中序遍历的访问顺序也可以是：中序遍历右子树、根节点、中序遍历左子树。这样访问上面的结果为12、11、10、9、8 、7、5、4、3、2、1，可见二叉搜索树的中序遍历结果是升序或者降序的。
中序遍历的代码实现：
/**
* 中序遍历
*/
public void inorder() {
inorder(root);
}
private void inorder(Node<E> node) {
if(null == node) {
return;
}
if(null != node.left) {
inorder(node.left);
}
System.out.println(node.value);
if(null != node.right) {
inorder(node.right);
}
}
后序遍历
后序遍历的访问顺序：后序遍历左子树、后序遍历右子树、父节点。
下面的二叉树后序遍历的结果为1、3、2、5、4、8、10、12、11、9、7。
后序遍历的代码实现：
/**
* 后序遍历
*/
public void postorder() {
postorder(root);
}
private void postorder(Node<E> node) {
if(null == node) {
return;
}
if(null != node.left) {
postorder(node.left);
}
if(null != node.right) {
postorder(node.right);
}
System.out.println(node.value);
}
层序遍历
层序遍历的访问顺序：从上到下、从左到右依次访问每一个节点
下面的二叉树层序遍历的结果为7、4、9、2、5、8、11、1、3、10、12
层序遍历的思路：使用队列
将根节点入队
循环执行以下操作，直到队列为空
将队头节点A出队，进行访问
将A的左子节点入队
将A的右子节点入队
层序遍历的代码实现：
/**
* 层序遍历
*/
public void levelOrder() {
if (null == root) {
return;
}
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.value);
if(null != node.left) {
queue.offer(node.left);
}
if(null != node.right) {
queue.offer(node.right);
}
}
}