1 package com.pow2.structures.tree;
2
3
4 /***
5 * Binary search tree class.
6 * <br>
7 * Traverse this tree using post-order algorithm.
8 *
9 * @author particle@theparticle.com (http://www.theparticle.com/)
10 */
11 public class BinarySearchTree extends BinaryTree
12 {
13 /***
14 * Constructor for the BinarySearchTree object
15 */
16 public BinarySearchTree()
17 {
18 super();
19 }
20
21
22 /***
23 * Constructor for the BinarySearchTree object
24 *
25 * @param o the root node of the tree.
26 */
27 public BinarySearchTree(Object o)
28 {
29 super(o);
30 }
31
32
33 /***
34 * Insert a Comparable object into the tree.
35 *
36 * @param o the Comparable object to insert.
37 */
38 public void insert(Comparable o)
39 {
40 Node t;
41 Node q;
42
43 // loop condition:
44 // a) 't' does not equal to null.
45 // b) the object we're trying to insert does not equal to
46 // the object already inside the tree.
47
48 // inside the loop (update statements):
49 // set 'q' to the value of the next node to be examined.
50 // Do this by first comparing the data we're inserting with the data in the current node;
51 // if it's greater, we set 't' to the right node, if less, we set it to the left node.
52
53 for (q = null, // initialize;
54 t = getRoot(); // condition;
55 t != null && o.compareTo(t.getData()) != 0; // update;
56 q = t, //
57 t = (o.compareTo(t.getData()) < 0) ? t.getLeft() : t.getRight()); //
58
59 if (t != null) { return; } // check to see if we've gotten to the end (or leaf) of the tree.
60 else if (q == null) { setRoot(new Node(o)); } // check to see if the tree is empty.
61 else if (o.compareTo(q.getData()) < 0) { insertLeft(q, new Node(o)); } // else insert the object into the left
62 else { insertRight(q, new Node(o)); } // or the right child of the leaf node depending on the value of the data.
63 }
64
65
66 /***
67 * Visit the content of the input node.
68 *
69 * @param p the visited node.
70 */
71 public void visit(Node n)
72 {
73 System.out.println(n.getData() + " ");
74 }
75
76
77 /***
78 * Build the tree
79 */
80 public void build()
81 {
82 }
83 }