服務熱線02152235399
package edu.cumt.jnotnull;
1.
2. import java.util.Stack;
3.
4. public class BinaryTree {
5. protected Node root;
6.
7. public BinaryTree(Node root) {
8. this.root = root;
9. }
10.
11. public Node getRoot() {
12. return root;
13. }
14.
15. /** 構造樹 */
16. public static Node init() {
17. Node a = new Node('A');
18. Node b = new Node('B', null, a);
19. Node c = new Node('C');
20. Node d = new Node('D', b, c);
21. Node e = new Node('E');
22. Node f = new Node('F', e, null);
23. Node g = new Node('G', null, f);
24. Node h = new Node('H', d, g);
25. return h;// root
26. }
27.
28. /** 訪問節點 */
29. public static void visit(Node p) {
30. System.out.print(p.getKey() + " ");
31. }
32.
33. /** 遞歸實現前序遍歷 */
34. protected static void preorder(Node p) {
35. if (p != null) {
36. visit(p);
37. preorder(p.getLeft());
38. preorder(p.getRight());
39. }
40. }
41.
42. /** 遞歸實現中序遍歷 */
43. protected static void inorder(Node p) {
44. if (p != null) {
45. inorder(p.getLeft());
46. visit(p);
47. inorder(p.getRight());
48. }
49. }
50.
51. /** 遞歸實現后序遍歷 */
52. protected static void postorder(Node p) {
53. if (p != null) {
54. postorder(p.getLeft());
55. postorder(p.getRight());
56. visit(p);
57. }
58. }
59.
60. /** 非遞歸實現前序遍歷 */
61. protected static void iterativePreorder(Node p) {
62. Stack<Node> stack = new Stack<Node>();
63. if (p != null) {
64. stack.push(p);
65. while (!stack.empty()) {
66. p = stack.pop();
67. visit(p);
68. if (p.getRight() != null)
69. stack.push(p.getRight());
70. if (p.getLeft() != null)
71. stack.push(p.getLeft());
72. }
73. }
74. }
75.
76. /** 非遞歸實現前序遍歷2 */
77. protected static void iterativePreorder2(Node p) {
78. Stack<Node> stack = new Stack<Node>();
79. Node node = p;
80. while (node != null || stack.size() > 0) {
81. while (node != null) {//壓入所有的左節點，壓入前訪問它
82. visit(node);
83. stack.push(node);
84. node = node.getLeft();
85. }
86. if (stack.size() > 0) {//
87. node = stack.pop();
88. node = node.getRight();
89. }
90. }
91. }
92.
93. /** 非遞歸實現后序遍歷 */
94. protected static void iterativePostorder(Node p) {
95. Node q = p;
96. Stack<Node> stack = new Stack<Node>();
97. while (p != null) {
98. // 左子樹入棧
99. for (; p.getLeft() != null; p = p.getLeft())
100. stack.push(p);
101. // 當前節點無右子或右子已經輸出
102. while (p != null && (p.getRight() == null || p.getRight() == q)) {
103. visit(p);
104. q = p;// 記錄上一個已輸出節點
105. if (stack.empty())
106. return;
107. p = stack.pop();
108. }
109. // 處理右子
110. stack.push(p);
111. p = p.getRight();
112. }
113. }
114.
115. /** 非遞歸實現后序遍歷 雙棧法 */
116. protected static void iterativePostorder2(Node p) {
117. Stack<Node> lstack = new Stack<Node>();
118. Stack<Node> rstack = new Stack<Node>();
119. Node node = p, right;
120. do {
121. while (node != null) {
122. right = node.getRight();
123. lstack.push(node);
124. rstack.push(right);
125. node = node.getLeft();
126. }
127. node = lstack.pop();
128. right = rstack.pop();
129. if (right == null) {
130. visit(node);
131. } else {
132. lstack.push(node);
133. rstack.push(null);
134. }
135. node = right;
136. } while (lstack.size() > 0 || rstack.size() > 0);
137. }
138.
139. /** 非遞歸實現后序遍歷 單棧法*/
140. protected static void iterativePostorder3(Node p) {
141. Stack<Node> stack = new Stack<Node>();
142. Node node = p, prev = p;
143. while (node != null || stack.size() > 0) {
144. while (node != null) {
145. stack.push(node);
146. node = node.getLeft();
147. }
148. if (stack.size() > 0) {
149. Node temp = stack.peek().getRight();
150. if (temp == null || temp == prev) {
151. node = stack.pop();
152. visit(node);
153. prev = node;
154. node = null;
155. } else {
156. node = temp;
157. }
158. }
159.
160. }
161. }
162.
163. /** 非遞歸實現后序遍歷4 雙棧法*/
164. protected static void iterativePostorder4(Node p) {
165. Stack<Node> stack = new Stack<Node>();
166. Stack<Node> temp = new Stack<Node>();
167. Node node = p;
168. while (node != null || stack.size() > 0) {
169. while (node != null) {
170. temp.push(node);
171. stack.push(node);
172. node = node.getRight();
173. }
174. if (stack.size() > 0) {
175. node = stack.pop();
176. node = node.getLeft();
177. }
178. }
179. while (temp.size() > 0) {
180. node = temp.pop();
181. visit(node);
182. }
183. }
184.
185. /** 非遞歸實現中序遍歷 */
186. protected static void iterativeInorder(Node p) {
187. Stack<Node> stack = new Stack<Node>();
188. while (p != null) {
189. while (p != null) {
190. if (p.getRight() != null)
191. stack.push(p.getRight());// 當前節點右子入棧
192. stack.push(p);// 當前節點入棧
193. p = p.getLeft();
194. }
195. p = stack.pop();
196. while (!stack.empty() && p.getRight() == null) {
197. visit(p);
198. p = stack.pop();
199. }
200. visit(p);
201. if (!stack.empty())
202. p = stack.pop();
203. else
204. p = null;
205. }
206. }
207.
208. /** 非遞歸實現中序遍歷2 */
209. protected static void iterativeInorder2(Node p) {
210. Stack<Node> stack = new Stack<Node>();
211. Node node = p;
212. while (node != null || stack.size() > 0) {
213. while (node != null) {
214. stack.push(node);
215. node = node.getLeft();
216. }
217. if (stack.size() > 0) {
218. node = stack.pop();
219. visit(node);
220. node = node.getRight();
221. }
222. }
223. }
224.
225. /**
226. * @param args
227. */
228. public static void main(String[] args) {
229. BinaryTree tree = new BinaryTree(init());
230. System.out.print(" Pre-Order:");
231. preorder(tree.getRoot());
232. System.out.println();
233. System.out.print(" In-Order:");
234. inorder(tree.getRoot());
235. System.out.println();
236. System.out.print("Post-Order:");
237. postorder(tree.getRoot());
238. System.out.println();
239. System.out.print(" Pre-Order:");
240. iterativePreorder(tree.getRoot());
241. System.out.println();
242. System.out.print("Pre-Order2:");
243. iterativePreorder2(tree.getRoot());
244. System.out.println();
245. System.out.print(" In-Order:");
246. iterativeInorder(tree.getRoot());
247. System.out.println();
248. System.out.print(" In-Order2:");
249. iterativeInorder2(tree.getRoot());
250. System.out.println();
251. System.out.print(" Post-Order:");
252. iterativePostorder(tree.getRoot());
253. System.out.println();
254. System.out.print("Post-Order2:");
255. iterativePostorder2(tree.getRoot());
256. System.out.println();
257. System.out.print("Post-Order3:");
258. iterativePostorder3(tree.getRoot());
259. System.out.println();
260. System.out.print("Post-Order4:");
261. iterativePostorder4(tree.getRoot());
262. System.out.println();
263.
264. }
265.
266. }
1. package edu.cumt.jnotnull;
2.
3. public class Node {
4. private char key;
5. private Node left, right;
6.
7. public Node(char key) {
8. this(key, null, null);
9. }
10.
11. public Node(char key, Node left, Node right) {
12. this.key = key;
13. this.left = left;
14. this.right = right;
15. }
16.
17. public char getKey() {
18. return key;
19. }
20.
21. public void setKey(char key) {
22. this.key = key;
23. }
24.
25. public Node getLeft() {
26. return left;
27. }
28.
29. public void setLeft(Node left) {
30. this.left = left;
31. }
32.
33. public Node getRight() {
34. return right;
35. }
36.
37. public void setRight(Node right) {
38. this.right = right;
39. }
40. }