二叉樹是數據結構世界中具有重要地位的一種數據結構。它同時具備有序數組和鏈表的優點，同時又彌補了有序數組插入數據、鏈表查找的缺點。同時也是各種面試中常見的問題。現通過java實現二叉樹，加深對二叉樹的理解。
代碼實現：
1
package com.zxl.algorithm;
2
3import java.util.LinkedList;
4import java.util.List;
5import org.apache.log4j.Logger;
6
7
/** *//**
8
* 二叉樹
9 *
10 * @author zhangxl
11 * @version 1.0.0
12 * @param <E>
13
*/
14public class BinaryTree<E extends Comparable<E>>
15
{
16 private static final Logger logger = Logger.getLogger(BinaryTree.class);
17
18 private Node<E> root;
19
20 public void insert(E e)
21
{
22 if(e == null)
23 {
24 throw new IllegalArgumentException("BinaryTree's data cann't be null!");
25
}
26
27 /**//* 不存在根節點，首先創建根節點 */
28 if(root == null)
29 {
30 root = new Node<E>(null, e);
31 }
32 else
33 {
34 Node<E> current = root;
35 Node<E> parent;
36 while(true)
37 {
38 parent = current;
39 if(e.compareTo(parent.getData()) == 0)
40 {
41 throw new IllegalArgumentException("Node[" + e.toString() + "] to build has already existed!existing obj [" + parent.getData().toString() + "]");
42 }
43 else if(e.compareTo(parent.getData()) < 0)
44 {
45 current = current.leftChild;
46 if(current == null)
47 {
48 Node<E> newNode = new Node<E>(parent, e);
49 parent.leftChild = newNode;
50 return;
51 }
52 }
53 else
54 {
55 current = current.rightChild;
56 if(current == null)
57 {
58 Node<E> newNode = new Node<E>(parent, e);
59 parent.rightChild = newNode;
60 return;
61 }
62 }
63 }
64 }
65 }
66
67 /** *//**
68 * 中序遍歷(LDR)
69 *
70 * @return
71 */
72 public List<E> inOrder()
73 {
74 List<E> list = new LinkedList<E>();
75 inOrderTraverse(root.leftChild, list);
76 list.add(root.data);
77 inOrderTraverse(root.rightChild, list);
78
79 return list;
80 }
81
82 private void inOrderTraverse(Node<E> node, List<E> list)
83 {
84 if(node != null)
85 {
86 inOrderTraverse(node.leftChild, list);
87 list.add(node.data);
88 inOrderTraverse(node.rightChild, list);
89 }
90 }
91
92 /** *//**
93 * 前序遍歷(DRL)
94 *
95 * @return
96 */
97 public List<E> preOrder()
98 {
99 List<E> list = new LinkedList<E>();
100 if(root == null)
101 {
102 return list;
103 }
104
105 list.add(root.data);
106 preOrderTraverse(root.leftChild, list);
107 preOrderTraverse(root.rightChild, list);
108
109 return list;
110
111 }
112
113 private void preOrderTraverse(Node<E> node, List<E> list)
114 {
115 if(node != null)
116 {
117 list.add(node.getData());
118 preOrderTraverse(node.leftChild, list);
119 preOrderTraverse(node.rightChild, list);
120 }
121 }
122
123 /** *//**
124 * 后序遍歷(LRD)
125 *
126 * @return
127 */
128 public List<E> postOrder()
129 {
130 List<E> list = new LinkedList<E>();
131 if(root == null)
132 {
133 return list;
134 }
135
136 postOrderTraverse(root.leftChild, list);
137 postOrderTraverse(root.rightChild, list);
138 list.add(root.getData());
139
140 return list;
141 }
142
143 private void postOrderTraverse(Node<E> node, List<E> list)
144 {
145 if(node != null)
146 {
147 postOrderTraverse(node.leftChild, list);
148 postOrderTraverse(node.rightChild, list);
149 list.add(node.getData());
150 }
151 }
152
153 /** *//**
154 * 刪除節點
155 *
156 * @param e
157 */
158 public void delete(E e)
159 {
160 if(e == null)
161 {
162 return;
163 }
164
165 // TODO
166
167 }
168
169 /** *//**
170 * 查找節點
171 *
172 * @param e
173 * @return
174 */
175 public BinaryTree<E>.Node<E> find(E e)
176 {
177 Node<E> current = root;
178 while(e.equals(current.data))
179 {
180 if(e.compareTo(current.data) < 0)
181 {
182 current = current.leftChild;
183 }
184 else
185 {
186 current = current.rightChild;
187 }
188
189 if(current == null)
190 {
191 return null;
192 }
193 }
194 return current;
195 }
196
197 /** *//**
198 * 二叉樹Node節點
199 *
200 * @author Administrator
201 *
202 * @param <E>
203 */
204 class Node<E>
205 {
206 private Node<E> parent;
207
208 private Node<E> leftChild;
209
210 private Node<E> rightChild;
211
212 private E data;
213
214 public Node(Node<E> parent, E data)
215 {
216 this.parent = parent;
217 this.data = data;
218 }
219
220 public Node<E> getParent()
221 {
222 return parent;
223 }
224
225 public void setParent(Node<E> parent)
226 {
227 this.parent = parent;
228 }
229
230 public Node<E> getLeftChild()
231 {
232 return leftChild;
233 }
234
235 public void setLeftChild(Node<E> leftChild)
236 {
237 this.leftChild = leftChild;
238 }
239
240 public Node<E> getRightChild()
241 {
242 return rightChild;
243 }
244
245 public void setRightChild(Node<E> rightChild)
246 {
247 this.rightChild = rightChild;
248 }
249
250 public E getData()
251 {
252 return data;
253 }
254
255 public void setData(E data)
256 {
257 this.data = data;
258 }
259
260 }
261
262 public static void main(String args)
263 {
264 BinaryTree<Integer> bt = new BinaryTree<Integer>();
265 bt.insert(new Integer(66));
266 bt.insert(Integer.valueOf(50));
267 bt.insert(Integer.valueOf(6));
268 bt.insert(Integer.valueOf(14));
269 bt.insert(Integer.valueOf(88));
270 bt.insert(Integer.valueOf(52));
271 bt.insert(Integer.valueOf(108));
272 bt.insert(Integer.valueOf(76));
273
274 List<Integer> list = bt.inOrder();
275 StringBuffer buffer = new StringBuffer();
276 for(int i = 0; i < list.size(); i++)
277 {
278 if(buffer.length() > 0)
279 {
280 buffer.append(",");
281 }
282 buffer.append(list.get(i));
283 }
284
285 System.out.println("中序遍歷：" + buffer.toString());
286
287 list = bt.preOrder();
288 buffer = new StringBuffer();
289 for(int i = 0; i < list.size(); i++)
290 {
291 if(buffer.length() > 0)
292 {
293 buffer.append(",");
294 }
295 buffer.append(list.get(i));
296 }
297
298 System.out.println("前序遍歷：" + buffer.toString());
299
300 list = bt.postOrder();
301 buffer = new StringBuffer();
302 for(int i = 0; i < list.size(); i++)
303 {
304 if(buffer.length() > 0)
305 {
306 buffer.append(",");
307 }
308 buffer.append(list.get(i));
309 }
310
311 System.out.println("后序遍歷：" + buffer.toString());
312 }
313
314}
315 輸出結果：
中序遍歷：6,14,50,52,66,76,88,108
前序遍歷：66,50,6,14,52,88,76,108
后序遍歷：14,6,52,50,76,108,88,66
/**********************************************/
posted on 2014-04-18 18:34
zhangxl 閱讀(337)
評論(0) 編輯 收藏 所屬分類:
arithmetics