二叉树的四种遍历（递归与非递归）

　　先序遍历与后序遍历
　　先序遍历根节点，再遍历左子树，再遍历右子树。
　　后序遍历先遍历左子树，再遍历右子树，再遍历根节点。
　　先序遍历递归实现： public static void preOrderByRecursion(TreeNode root) {     // 打印节点值     System.out.println(root.value);     preOrder(root.left);     preOrder(root.right); }
　　先序遍历的非递归实现：
　　非递归实现需要借助栈这样一个数据结构，实际上递归实现也是依靠栈，只不过是隐式的。 先将根节点压入栈中。 弹出栈中的节点，将弹出节点的右子节点压入栈中，再将弹出节点的左子树压入栈中。 重复步骤2，直到栈为空。 public static void preOrder(TreeNode root) {     if (root == null) {         return;     }     Stack stack = new Stack<>();     stack.push(root);     while (!stack.empty()) {         TreeNode node = stack.pop();         // 打印节点值         System.out.print(node.value + ＂ ＂);         if (node.right != null) {             stack.push(node.right);         }         if (node.left != null) {             stack.push(node.left);         }     } }
　　后序遍历递归实现：先序遍历反过来，就不赘述了。 public static void postOrderByRecursion(TreeNode root) {     postOrderByRecursion(root.left);     postOrderByRecursion(root.right);     System.out.println(root.value); }
　　后序遍历非递归实现：后序遍历就是先序遍历反过来，所以需要两个栈，多出来的栈用来反向输出。 public static void postOrder(TreeNode root) {     if (root == null) {         return;     }     Stack s1 = new Stack<>();     Stack s2 = new Stack<>();     s1.push(root);     while (!s1.empty()) {         TreeNode node = s1.pop();         s2.push(node);         if (node.left != null) {             s1.push(node.left);         }         if (node.right != null) {             s1.push(node.right);         }     }     while (!s2.empty()) {         System.out.println(s2.pop().value);     } } 中序遍历
　　中序遍历先遍历左子树，再遍历根节点，再遍历右子树。
　　递归遍历： public static void inOrderByRecursion(TreeNode root) {     if (root == null) {         return;     }     inOrderByRecursion(root.left);     // 打印节点值     System.out.println(root.value);     inOrderByRecursion(root.right); }
　　非递归遍历： 将二叉树的左侧＂边＂从上到下依次压入栈中。 从栈中弹出节点 对以弹出节点的右子节点为根节点的子树，重复步骤1。 重复2、3步骤，直到栈为空。 public static void inOrder(TreeNode root) {     if (root == null) {         return;     }     Stack stack = new Stack<>();     TreeNode cur = root;      while (cur != null) {         stack.push(cur);         cur = cur.left;     }      while (!stack.empty()) {         TreeNode node = stack.pop();         System.out.println(node.value);         cur = node.right;         while (cur != null) {             stack.push(cur);             cur = cur.left;         }     } } 层序遍历
　　层序遍历顾名思义就是一层一层，从左到右的遍历二叉树。需要用到队列这一数据结构。 将根节点推入队列。 从队列中取出一个节点。 先将取出节点的左子节点推入队列，再将取出节点的右子节点推入队列。 重复2、3步骤直到队列中无节点可取。 public static void floorOrder(TreeNode root) {     if (root == null) {         return;     }     Queue queue = new LinkedList<>();     queue.add(root);     while (!queue.isEmpty()) {         TreeNode node = queue.poll();         System.out.println(node.value);         if (node.left != null) {             queue.add(node.left);         }         if (node.right != null) {             queue.add(node.right);         }     } }