二叉树的遍历方式:
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<BinaryTreeNode> 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<BinaryTreeNode> 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<BinaryTreeNode> 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<BinaryTreeNode> stack = new Stack<>();
133 Stack<BinaryTreeNode> temp = new Stack<>();
134 BinaryTreeNode node = root;
135 while (node != null || stack.size() &g