Java版 二叉樹 所有遞歸和非遞歸遍歷算法

通過數組構造二叉樹，所有遍歷算法以及求二叉樹深度的遞歸算法

1. import java.util.LinkedList;
4. public class BinaryTree {
6. private Node<Integer> root;
8. private int size;
10. public BinaryTree() {
11. root = new Node<Integer>();
12. }
14. public BinaryTree(int[] values) {
15. System.out.print("新建binaryTree:");
16. for (int i : values) {
17. System.out.print(i);
18. }
19. System.out.println();
20. boolean isLeft = true;
21. int len = values.length;
22. if (len == 0)
23. return ;
24. LinkedList<Node<Integer>> queue = new LinkedList<Node<Integer>>();
25. root = new Node<Integer>(values[0]);
26. queue.addLast(root);
27. Node parent = null;
28. Node current = null;
29. for (int i=1; i<len; i++) {
30. current = new Node<Integer>(values[i]);
31. queue.addLast(current);
32. if (isLeft)
33. parent = queue.getFirst();
34. else
35. parent = queue.removeFirst();
36. if (isLeft) {
37. parent.setLeftChild(current);
38. isLeft = false;
39. }else {
40. parent.setRightChild(current);
41. isLeft = true;
42. }
43. }
44. }
46. public void inorder() {
47. System.out.print("binaryTree遞歸中序遍歷:");
48. inorderTraverseRecursion(root);
49. System.out.println();
50. }
52. public void layerorder() {
53. System.out.print("binaryTree層次遍歷:");
54. LinkedList<Node<Integer>> queue = new LinkedList<Node<Integer>>();
55. queue.addLast(root);
56. Node<Integer> current = null;
57. while(!queue.isEmpty()) {
58. current = queue.removeFirst();
59. if (current.getLeftChild() != null)
60. queue.addLast(current.getLeftChild());
61. if (current.getRightChild() != null)
62. queue.addLast(current.getRightChild());
63. System.out.print(current.getValue());
64. }
65. System.out.println();
66. }
68. public int getLength() {
69. return getLengthRecursion(root);
70. }
72. private int getLengthRecursion(Node<Integer> node){
73. if (node == null)
74. return 0;
75. int llen = getLengthRecursion(node.getLeftChild());
76. int rlen = getLengthRecursion(node.getRightChild());
77. int maxlen = Math.max(llen, rlen);
78. return maxlen + 1;
79. }
80. public void preorder() {
81. System.out.print("binaryTree遞歸先序遍歷:");
82. preorderTraverseRecursion(root);
83. System.out.println();
84. }
86. private void inorderTraverseRecursion(Node<Integer> node) {
87. // TODO Auto-generated method stub
88. if (node.getLeftChild() != null)
89. inorderTraverseRecursion(node.getLeftChild());
90. System.out.print(node.getValue());
91. if (node.getRightChild() != null)
92. inorderTraverseRecursion(node.getRightChild());
93. }
96. private void preorderTraverseRecursion(Node<Integer> node){
97. System.out.print(node.getValue());
98. if (node.getLeftChild() != null)
99. preorderTraverseRecursion (node.getLeftChild());
100. if (node.getRightChild() != null)
101. preorderTraverseRecursion (node.getRightChild());
102. }
104. public void preorderNoRecursion() {
105. System.out.print("binaryTree非遞歸先序遍歷:");
106. LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
107. stack.push(root);
108. Node<Integer> current = null;
109. while (!stack.isEmpty()) {
110. current = stack.pop();
111. System.out.print(current.getValue());
112. if (current.getRightChild() != null)
113. stack.push(current.getRightChild());
114. if (current.getLeftChild() != null)
115. stack.push(current.getLeftChild());
116. }
117. System.out.println();
118. }
120. /**
121. * 棧內保存將要訪問的元素
122. */
123. public void inorderNoRecursion() {
124. System.out.print("binaryTree非遞歸中序遍歷:");
125. LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
126. Node<Integer> current = root;
127. while (current != null || !stack.isEmpty()) {
128. while(current != null) {
129. stack.push(current);
130. current = current.getLeftChild();
131. }
132. if (!stack.isEmpty()) {
133. current = stack.pop();
134. System.out.print(current.getValue());
135. current = current.getRightChild();
136. }
137. }
138. System.out.println();
139. }
141. /**
142. * 當上一個訪問的結點是右孩子或者當前結點沒有右孩子則訪問當前結點
143. */
144. public void postorderNoRecursion() {
145. System.out.print("binaryTree非遞歸後序遍歷:");
146. Node<Integer> rNode = null;
147. Node<Integer> current = root;
148. LinkedList<Node<Integer>> stack = new LinkedList<Node<Integer>>();
149. while(current != null || !stack.isEmpty()) {
150. while(current != null) {
151. stack.push(current);
152. current = current.getLeftChild();
153. }
154. current = stack.pop();
155. while (current != null && (current.getRightChild() == null ||current.getRightChild() == rNode)) {
156. System.out.print(current.getValue());
157. rNode = current;
158. if (stack.isEmpty()){
159. System.out.println();
160. return;
161. }
162. current = stack.pop();
163. }
164. stack.push(current);
165. current = current.getRightChild();
166. }
168. }
170. public static void main(String[] args) {
171. BinaryTree bt = new BinaryTree(new int[]{1,2,3,4,5,6,7,8});
172. bt.inorder();
173. bt.preorder();
174. bt.layerorder();
175. bt.preorderNoRecursion();
176. bt.inorderNoRecursion();
177. bt.postorderNoRecursion();
178. System.out.println("深度為：" + bt.getLength());
179. }
180. }
182. class Node<V>{
183. private V value;
184. private Node<V> leftChild;
185. private Node<V> rightChild;
187. public Node(){
188. };
190. public Node(V value) {
191. this.value = value;
192. leftChild = null;
193. rightChild = null;
194. }
196. public void setLeftChild(Node<V> lNode) {
197. this.leftChild = lNode;
198. }
200. public void setRightChild(Node<V> rNode) {
201. this.rightChild = rNode;
202. }
204. public V getValue() {
205. return value;
206. }
208. public void setValue(V value) {
209. this.value = value;
210. }
212. public Node<V> getLeftChild() {
213. return leftChild;
214. }
216. public Node<V> getRightChild() {
217. return rightChild;
218. }
221. }