二叉树的遍历方式：
1、深度优先：递归，非递归实现方式
1)先序遍历：先访问根节点，再依次访问左子树和右子树
2)中序遍历：先访问左子树，再访问根节点吗，最后访问右子树
3)后序遍历：先访问左子树，再访问右子树，最后访问根节点
2、广度优先
按照树的深度，一层一层的访问树的节点
1 package Solution; 2 3 import java.util.LinkedList; 4 import java.util.Queue; 5 import java.util.Stack; 6 7 8 public class BinaryTree { 9 10 // 二叉树节点 11 public static class BinaryTreeNode { 12 int value; 13 BinaryTreeNode left; 14 BinaryTreeNode right; 15 16 public BinaryTreeNode(int value) { 17 this.value = value; 18 } 19 20 public BinaryTreeNode(int value, BinaryTreeNode left, 21 BinaryTreeNode right) { 22 super(); 23 this.value = value; 24 this.left = left; 25 this.right = right; 26 } 27 28 } 29 30 // 访问树的节点 31 public static void visit(BinaryTreeNode node) { 32 System.out.println(node.value); 33 } 34 35 /** 递归实现二叉树的先序遍历 */ 36 public static void preOrder(BinaryTreeNode node) { 37 if (node != null) { 38 visit(node); 39 preOrder(node.left); 40 preOrder(node.right); 41 } 42 } 43 44 /** 递归实现二叉树的中序遍历 */ 45 public static void inOrder(BinaryTreeNode node) { 46 if (node != null) { 47 inOrder(node.left); 48 visit(node); 49 inOrder(node.right); 50 } 51 } 52 53 /** 递归实现二叉树的后序遍历 */ 54 public static void postOrder(BinaryTreeNode node) { 55 if (node != null) { 56 postOrder(node.left); 57 postOrder(node.right); 58 visit(node); 59 } 60 } 61 62 /** 非递归实现二叉树的先序遍历 */ 63 public static void iterativePreorder(BinaryTreeNode node) { 64 Stack stack = new Stack<>(); 65 if (node != null) { 66 stack.push(node); 67 while (!stack.empty()) { 68 node = stack.pop(); 69 // 先访问节点 70 visit(node); 71 // 把右子结点压入栈 72 if (node.right != null) { 73 stack.push(node.right); 74 } 75 // 把左子结点压入栈 76 if (node.left != null) { 77 stack.push(node.left); 78 } 79 } 80 } 81 } 82 83 /** 非递归实现二叉树的中序遍历 */ 84 public static void iterativeInOrder(BinaryTreeNode root) { 85 Stack stack = new Stack<>(); 86 BinaryTreeNode node = root; 87 while (node != null || stack.size() > 0) { 88 // 把当前节点的所有左侧子结点压入栈 89 while (node != null) { 90 stack.push(node); 91 node = node.left; 92 } 93 // 访问节点，处理该节点的右子树 94 if (stack.size() > 0) { 95 node = stack.pop(); 96 visit(node); 97 node = node.right; 98 } 99 }100 }101 102 /** 非递归使用单栈实现二叉树后序遍历 */103 public static void iterativePostOrder(BinaryTreeNode root) {104 Stack stack = new Stack<>();105 BinaryTreeNode node = root;106 // 访问根节点时判断其右子树是够被访问过107 BinaryTreeNode preNode = null;108 while (node != null || stack.size() > 0) {109 // 把当前节点的左侧节点全部入栈110 while (node != null) {111 stack.push(node);112 node = node.left;113 }114 if (stack.size() > 0) {115 BinaryTreeNode temp = stack.peek().right;116 // 一个根节点被访问的前提是：无右子树或右子树已被访问过117 if (temp == null || temp == preNode) {118 node = stack.pop();119 visit(node);120 preNode = node;// 记录刚被访问过的节点121 node = null;122 } else {123 // 处理右子树124 node = temp;125 }126 }127 }128 }129 130 /** 非递归使用双栈实现二叉树后序遍历 */131 public static void iterativePostOrderByTwoStacks(BinaryTreeNode root) {132 Stack stack = new Stack<>();133 Stack temp = new Stack<>();134 BinaryTreeNode node = root;135 while (node != null || stack.size() > 0) {136 // 把当前节点和其右侧子结点推入栈137 while (node != null) {138 stack.push(node);139 temp.push(node);140 node = node.right;141 }142 // 处理栈顶节点的左子树143 if (stack.size() > 0) {144 node = stack.pop();145 node = node.left;146 }147 }148 while (temp.size() > 0) {149 node = temp.pop();150 visit(node);151 }152 }153 154 /** 二叉树广度优先遍历——层序遍历 */155 public static void layerTraversal(BinaryTreeNode root) {156 Queue queue = new LinkedList<>();157 158 if (root != null) {159 queue.add(root);160 while (!queue.isEmpty()) {161 BinaryTreeNode currentNode = queue.poll();162 visit(currentNode);163 if (currentNode.left != null) {164 queue.add(currentNode.left);165 }166 167 if (currentNode.right != null) {168 queue.add(currentNode.right);169 }170 171 }172 }173 }174 175 public static void main(String[] args) {176 177 // 构造二叉树178 // 1179 // / \180 // 2 3181 // / / \182 // 4 5 7183 // \ /184 // 6 8185 BinaryTreeNode root = new BinaryTreeNode(1);186 BinaryTreeNode node2 = new BinaryTreeNode(2);187 BinaryTreeNode node3 = new BinaryTreeNode(3);188 BinaryTreeNode node4 = new BinaryTreeNode(4);189 BinaryTreeNode node5 = new BinaryTreeNode(5);190 BinaryTreeNode node6 = new BinaryTreeNode(6);191 BinaryTreeNode node7 = new BinaryTreeNode(7);192 BinaryTreeNode node8 = new BinaryTreeNode(8);193 194 root.left = node2;195 root.right = node3;196 node2.left = node4;197 node3.left = node5;198 node3.right = node7;199 node5.right = node6;200 node7.left = node8;201 System.out.println("二叉树先序遍历");202 preOrder(root);203 System.out.println("二叉树先序遍历非递归");204 iterativePreorder(root);205 System.out.println("二叉树中序遍历");206 inOrder(root);207 System.out.println("二叉树中序遍历非递归");208 iterativeInOrder(root);209 System.out.println("二叉树后序遍历");210 postOrder(root);211 System.out.println("二叉树单栈非递归后序遍历");212 iterativePostOrder(root);213 System.out.println("二叉树双栈非递归后序遍历");214 iterativePostOrderByTwoStacks(root);215 System.out.println("二叉树层树序遍历");216 layerTraversal(root);217 }218 }