1 /***
2 * The contents of this file are subject to the Mozilla Public
3 * License Version 1.1 (the "License"); you may not use this file
4 * except in compliance with the License. You may obtain a copy of
5 * the License at http://www.mozilla.org/MPL/
6 *
7 * Software distributed under the License is distributed on an "AS
8 * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
9 * implied. See the License for the specific language governing
10 * rights and limitations under the License.
11 *
12 * The Original Code is pow2toolkit library.
13 *
14 * The Initial Owner of the Original Code is
15 * particle (www.theparticle.com)
16 *
17 * Portions created by Power Of Two S.R.L. are
18 * Copyright (C) Power Of Two S.R.L.
19 * All Rights Reserved.
20 *
21 * Contributor(s):
22 */
23
24 package com.pow2.structures.tree;
25
26
27 import org.apache.log4j.Category;
28
29 /***
30 * Binary tree abstract class.
31 * <br>
32 * Extend this class and implement the {@link #build() build} method.
33 *
34 * @author <a mailto="particle@theparticle.com">particle</a>
35 * (<a href="http://www.theparticle.com/">www.theparticle.com</a>)
36 * @author Luca Fossato
37 * @created 06 July 2002
38 */
39 public abstract class BinaryTree
40 {
41 /*** Build the tree. */
42 public abstract void build();
43
44
45 /*** use this value to specify the pre-traverse algorithm */
46 public final static int PRETRAVERSE = 0;
47
48 /*** use this value to specify the in-traverse algorithm */
49 public final static int INTRAVERSE = 1;
50
51 /*** use this value to specify the post-traverse algorithm */
52 public final static int POSTRAVERSE = 2;
53
54 /*** Log4j category */
55 protected Category cat = Category.getInstance(BinaryTree.class.getName());
56
57 /*** The root node of the tree */
58 protected Node root;
59
60 /***
61 * Specify the tree traverse mode.
62 * <br>
63 * It can have one of the following values:
64 * <ul>
65 * <li>BynaryTree.PRETRAVERSE - use the pre-traverse algorithm</li>
66 * <li>BynaryTree.INTRAVERSE - use the in-traverse algorithm</li>
67 * <li>BynaryTree.POSTRAVERSE - use the post-traverse algorithm</li>
68 * </ul>
69 */
70 protected int traverseMode;
71
72 /*** the nodeVisitor reference */
73 protected NodeVisitorInterface nodeVisitor;
74
75
76 /***
77 * Default constructor for the BinaryTree object.
78 * <br>
79 * Set the traverse mode to <code>PRETRAVERSE</code>.
80 */
81 public BinaryTree()
82 {
83 root = null;
84 nodeVisitor = null;
85 traverseMode = PRETRAVERSE;
86 }
87
88
89 /***
90 * Constructor for BinaryTree object.
91 * <br>
92 * Set the input {@link java.lang.Object#Object() object} as the data object
93 * related to the root {@link Node#Node(Object) node} of the tree.
94 *
95 * @param o the data object to relate to the tree root node
96 */
97 public BinaryTree(Object o)
98 {
99 root = new Node(o);
100 root.setDepth(0);
101 }
102
103
104 /***
105 * Sets the data object of the tree root node.
106 * <br>
107 * If the tree root node is null, instance a new root node and set its
108 * data property.
109 *
110 * @param o The new root node data object
111 */
112 public void setData(Object o)
113 {
114 if (isEmpty())
115 root = new Node();
116 root.setData(o);
117 }
118
119
120 /***
121 * Sets the nodeVisitor attribute of the BinaryTree object
122 *
123 * @param nodeVisitor The new nodeVisitor value
124 */
125 public void setNodeVisitor(NodeVisitorInterface nodeVisitor)
126 {
127 this.nodeVisitor = nodeVisitor;
128 }
129
130
131 /***
132 * Set the root node of the BinaryTree object
133 *
134 * @param r The new root value
135 */
136 public void setRoot(Node r)
137 {
138 root = r;
139 }
140
141
142 /***
143 * Set the traverseMode attribute of the BinaryTree object.
144 * <code>traverseMode</code> can have one of the following values:
145 * <ul>
146 * <li>{@link #PRETRAVERSE BynaryTree.PRETRAVERSE} to use the pre-traverse algorithm</li>
147 * <li>{@link #INTRAVERSE BynaryTree.INTRAVERSE} to use the in-traverse algorithm</li>
148 * <li>{@link #POSTRAVERSE BynaryTree.POSTRAVERSE} to use the post-traverse algorithm</li>
149 * </ul>
150 *
151 * @param traverseMode the traversing mode.
152 */
153 public void setTraverseMode(int traverseMode)
154 {
155 this.traverseMode = traverseMode;
156 }
157
158
159 /***
160 * Test if the Binary Tree is empty.
161 * <br>
162 * A binary tree is empty if the root element of the tree is null.
163 *
164 * @return true if the the root element of the tree is null;
165 * false otherwise.
166 */
167 public boolean isEmpty()
168 {
169 return (root == null);
170 }
171
172
173 /***
174 * Gets the data object of the tree root node
175 *
176 * @return The data object of the tree root node,
177 * or null if the root node is null
178 */
179 public Object getData()
180 {
181 return (!isEmpty()) ? root.getData() : null;
182 }
183
184
185 /***
186 * Gets the nodeVisitor attribute of the BinaryTree object
187 *
188 * @return The nodeVisitor value
189 */
190 public NodeVisitorInterface getNodeVisitor()
191 {
192 return nodeVisitor;
193 }
194
195
196 /***
197 * Gets the left node of the root node
198 *
199 * @return The left node of the root node, or null if the
200 * root node is null
201 */
202 public Node getLeft()
203 {
204 return (!isEmpty()) ? root.getLeft() : null;
205 }
206
207
208 /***
209 * Get the root node of the BinaryTree object
210 *
211 * @return The root value
212 */
213 public Node getRoot()
214 {
215 return root;
216 }
217
218
219 /***
220 * Gets the right node of the root node
221 *
222 * @return The right node of the root node, or null if the root node
223 * is empty
224 */
225 public Node getRight()
226 {
227 return (!isEmpty()) ? root.getRight() : null;
228 }
229
230
231 /***
232 * Get the traverse mode attribute of the BinaryTree object.
233 *
234 * @return the traverse mode attribute of the BinaryTree object
235 */
236 public int getTraverseMode()
237 {
238 return traverseMode;
239 }
240
241
242 /***
243 * Insert a new left node into the tree.
244 *
245 * @param p the parent node where to insert the new left node
246 * @param c the new left node to add to the parent node
247 * @return true if the insertion is successfull;
248 * false otherwise
249 */
250 public boolean insertLeft(Node p, Node c)
251 {
252
253 if ((p == null) || (p.getLeft() != null))
254 return false;
255
256 p.setLeft(c);
257 c.setParent(p);
258 c.setDepth(p.getDepth() + 1);
259
260 return true;
261 }
262
263
264 /***
265 * Insert a new right node into the tree.
266 *
267 * @param p the parent node where to insert the new right node
268 * @param c the new right node to add to the parent node
269 * @return true if the insertion is successfull;
270 * false otherwise
271 */
272 public boolean insertRight(Node p, Node c)
273 {
274
275 if ((p == null) || (p.getRight() != null))
276 return false;
277
278 p.setRight(c);
279 c.setParent(p);
280 c.setDepth(p.getDepth());
281
282 return true;
283 }
284
285
286 /***
287 * Add a new left node to the parent node left node list.
288 *
289 * @param p the parent node
290 * @param c the left node to add to the parent node left node list
291 * @return true if the addition is successfull;
292 * false otherwise
293 */
294 public boolean addLeft(Node p, Node c)
295 {
296 if (p == null)
297 return false;
298
299
300
301
302 if (p.getLeft() != null)
303 return addRight(p.getLeft(), c);
304 else
305 return insertLeft(p, c);
306 }
307
308
309 /***
310 * Add a new right node to the parent node right node list.
311 *
312 * @param p the parent node
313 * @param c the node to add to the the parent node right node list
314 * @return true if the addition is successfull;
315 * false otherwise
316 */
317 public boolean addRight(Node p, Node c)
318 {
319 if (p == null)
320 return false;
321
322
323 while (p.getRight() != null)
324 {
325 p = p.getRight();
326 }
327
328 p.setRight(c);
329 c.setParent(p);
330 c.setDepth(p.getDepth());
331
332 return true;
333 }
334
335
336 /***
337 * Move the input <code>c</code> node
338 * over the new parent <code>p</code> node.
339 *
340 * @param p the new parent node for <code>c</code> node
341 * @param c the node to move
342 * @param isLeft true if <code>c</code> must be inserted
343 * as a left node of <code>p</code>;
344 * false if <code>c</code> must be inserted as right
345 * node of <code>p</code>
346 */
347 public void move(Node p, Node c, boolean isLeft)
348 {
349
350
351
352 detachNode(c);
353
354
355 if (p.getId().equals("0"))
356 {
357 addLeft(p, c);
358
359 }
360 else
361 {
362 if (isLeft)
363 addLeft(p, c);
364
365 else
366 addRight(p, c);
367 }
368 }
369
370
371 /***
372 * Remove the input node from the tree.
373 *
374 * @param n the node to remove
375 * @param recursive true to remove all the input node children;
376 * false otherwise
377 */
378 public void remove(Node n, boolean recursive)
379 {
380 if (n == null)
381 return;
382
383 Node l = n.getLeft();
384 Node r = n.getRight();
385
386 remove(n);
387 n.finalize();
388
389
390 if (recursive)
391 {
392 remove(l, recursive);
393 remove(r, recursive);
394 }
395 }
396
397
398 /***
399 * Remove the input node from the tree, rearranging
400 * the parent and the child nodes references.
401 *
402 * @param n the node to remove
403 */
404 protected void remove(Node n)
405 {
406 detachNode(n);
407 n.finalize();
408 }
409
410
411 /***
412 * Detach the input node from the tree, rearranging
413 * the parent and the child nodes references.
414 *
415 * @param n the node to remove
416 */
417 private void detachNode(Node n)
418 {
419 Node parent = n.getParent();
420 Node right = n.getRight();
421 Node left = n.getLeft();
422
423
424
425 if ((parent != null) && (n == parent.getLeft()))
426 parent.setLeft(right);
427
428
429
430 else if ((parent != null) && (n == parent.getRight()))
431 parent.setRight(right);
432
433 if (right != null)
434 right.setParent(parent);
435
436 n.setRight (null);
437 n.setParent (null);
438 }
439
440
441 /***
442 * Traverse the tree, using the traverse algorithm
443 * specified using {@link #setTraverseMode(int) setTraverseMode}.
444 *
445 * @exception Exception if any error occurs
446 */
447 public void traverse() throws Exception
448 {
449 switch (traverseMode)
450 {
451
452 case PRETRAVERSE:
453 pretrav(root);
454 break;
455
456 case INTRAVERSE:
457 intrav(root);
458 break;
459
460 case POSTRAVERSE:
461 postrav(root);
462 break;
463 }
464 }
465
466
467 /***
468 * Traverse the tree, using pre-order algorithm,
469 * starting from the input node.
470 * <br>
471 * pre-order traversal: first looks at the data (of the current node),
472 * then the left nodes, and then the right nodes.
473 *
474 * @param p the node where to start the tree traversing
475 * @exception Exception if any error occurs
476 */
477 protected void pretrav(Node p) throws Exception
478 {
479 if (p == null)
480 return;
481
482 visit(p);
483 pretrav(p.getLeft());
484 pretrav(p.getRight());
485 }
486
487
488 /***
489 * Traverse the tree, using in-order algorithm, starting from the input node.
490 * <br>
491 * in-order traversal: first look at the right nodes, then the nodes data,
492 * and then the left nodes.
493 *
494 * @param p the node where to start the tree traversing.
495 * @exception Exception if any error occurs
496 */
497 protected void intrav(Node p) throws Exception
498 {
499 if (p == null)
500 return;
501
502 intrav(p.getRight());
503 visit(p);
504 intrav(p.getLeft());
505 }
506
507
508 /***
509 * Traverse the tree, using post-order algorithm, starting from the input node.
510 * <br>
511 * post-order traversal: looks at the left child, then right child,
512 * and only then data.
513 *
514 * @param p the node where to start the tree traversing.
515 * @exception Exception if any error occurs
516 */
517 protected void postrav(Node p) throws Exception
518 {
519 if (p == null)
520 return;
521
522 postrav(p.getLeft());
523 postrav(p.getRight());
524 visit(p);
525 }
526
527
528 /***
529 * Visit the content of the input node.
530 *
531 * @param n the node to visit
532 * @exception Exception if any error occurs
533 */
534 public void visit(Node n) throws Exception
535 {
536 nodeVisitor.visit(n);
537 }
538 }