一、二叉树的遍历
遍历是数据结构中的常见的操作，把所有元素都访问一遍。
线性数据结构的遍历比较简单
①、正序遍历
②、逆序遍历
根据节点访问顺序的不同，二叉树的常见遍历方式用四种
①、前序遍历（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);}
（一）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);}
如果是访问顺序是下面这样呢？
中序遍历右子树、根节点、中序遍历左子树
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);}
二叉搜索树的中序遍历结果是升序或者降序的
（二）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);}
（三）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);}}}
打印二叉树工具
工具：/CoderMJLee/BinaryTrees使用步骤：①、调用BinaryTreeInfo接口
②、调用打印APIBinaryTrees.println(bst);
import parator;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) {parator = 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 pare(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;}}@Overridepublic Object root() {return root;}@Overridepublic Object left(Object node) {return ((Node<E>)node).left;}@Overridepublic Object right(Object node) {return ((Node<E>)node).right;}@Overridepublic 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+")";}}
测试打印二叉树：
import parator;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();}}
运行结果：
┌─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
上述的遍历只是从头遍历到尾部，一直遍历下去，无法停止【即上面有多少个元素就遍历多少次】。但是不可以随时终止这个遍历，如何实现随时终止遍历的操作呢？
//前序遍历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);}
import parator;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();}}
┌─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
