1 /*
  2  *BinaryTree.java of trees package
  3  */
  4 package trees;
  5 
  6 /**
  7  * Implementation of a basic binary tree data type
  8  *
  9  * @author notebook
 10  */
 11 public class BinaryTree<K, V> implements BinaryTreeADT<K, V> {
 12 
 13     private K key;
 14     private V value;
 15     private BinaryTree<K, V> lchild;
 16     private BinaryTree<K, V> rchild;
 17 
 18     /**
 19      * Create a new empty BinaryTree instance
 20      */
 21     public BinaryTree() {
 22         key = null;
 23     }
 24 
 25     /**
 26      * Computes the value of the key of the BinaryTree
 27      * @return the value of the key of the BinaryTree
 28      */
 29     public V value() {
 30         return value;
 31     }
 32 
 33     /**
 34      * Gives a value to the key of the BinaryTree
 35      * @param value is the value being assigned to the key of the BinaryTree
 36      */
 37     public void setValue(V value) {
 38         this.value = value;
 39     }
 40 
 41     /**
 42      * Determines whether the BinaryTree is empty or not
 43      * @return true if the BinaryTree is empty
 44      */
 45     public boolean empty() {
 46         return key == null;
 47     }
 48 
 49     /**
 50      * Computes the height of the BinaryTree
 51      * @return the height of the BinaryTree
 52      */
 53     public int height() {
 54         if (empty()) {
 55             return 0;
 56         } else {
 57             return 1 + max(lchild.height(), rchild.height());
 58         }
 59     }
 60 
 61     /**
 62      * Compares two integers and return the greater one
 63      * @param a is an integer
 64      * @param b is an integer
 65      * @return the greater integer among the two parameters
 66      */
 67     private int max(int a, int b) {
 68         if (a > b) {
 69             return a;
 70         } else {
 71             return b;
 72         }
 73     }
 74 
 75     /**
 76      * Prints the BinaryTree to the output stream in preorder traversal
 77      */
 78     public void preorder() {
 79         if (!empty()) {
 80             visit();
 81             lchild.preorder();
 82             rchild.preorder();
 83         }
 84     }
 85 
 86     /**
 87      * Prints the BinaryTree to the output stream in inorder traversal
 88      */
 89     public void inorder() {
 90         if (!empty()) {
 91             lchild.inorder();
 92             visit();
 93             rchild.inorder();
 94         }
 95     }
 96 
 97     /**
 98      * Prints the BinaryTree to the output stream in postorder traversal
 99      */
100     public void postorder() {
101         if (!empty()) {
102             lchild.postorder();
103             rchild.postorder();
104             visit();
105         }
106     }
107 
108     /**
109      * Adds a pair of key and value to the BinaryTree according to the
110      * specified direction
111      * @param key is the key being added
112      * @param value is the value being added with the key
113      * @param dir is the sequence of directions (l/r) that specifies the 
114      * location of the pair being added
115      */
116     public void addLR(K key, V value, String dir) throws BinaryTreeCreationException {
117         try {
118             if (dir.equals("")) {
119                 sprout(key, value);
120             } else if (dir.substring(0, 1).equalsIgnoreCase("L")) {
121                 lchild.addLR(key, value, dir.substring(1));
122             } else if (dir.substring(0, 1).equalsIgnoreCase("R")) {
123                 rchild.addLR(key, value, dir.substring(1));
124             } else {
125                 throw new BinaryTreeCreationException("### strange directional indicator: " + dir.substring(0, 1));
126             }
127         } catch (BinaryTreeCreationException e) {
128             throw new BinaryTreeCreationException("### no such location in the tree");
129         }
130     }
131 
132     /**
133      * Adds a pair of key and value to the BinaryTree with a random direction
134      * @param key is the key being added
135      * @param value is the value being added with the key
136      */
137     public void addND(K key, V value) {
138         if (empty()) {
139             sprout(key, value);
140         } else if (Math.random() < 0.5) {
141             lchild.addND(key, value);
142         } else {
143             rchild.addND(key, value);
144         }
145     }
146 
147     /**
148      * Adds a pair of key and value to the BinaryTree according to 
149      * the rules of a Binary Search Tree.
150      * @param key is the key being added
151      * @param value is the value being added with the key
152      */
153     public void addST(K key, V value) throws BinaryTreeCreationException {
154         if (empty()) {
155             sprout(key, value);
156         } else {
157             Comparable cey = (Comparable) key;
158             Comparable t = (Comparable) this.key;
159             if (cey.compareTo(t) < 0) {
160                 lchild.addST(key, value);
161             } else if (cey.compareTo(t) > 0) {
162                 rchild.addST(key, value);
163             } else {
164                 throw new BinaryTreeCreationException("### can't have equality in bst");
165             }
166         }
167     }
168 
169     /**
170      * Computes the value of the specified key
171      * @param key is the key that is used to find the value
172      * @return the value of the specified key
173      */
174     public V get(K key) {
175         BinaryTree<K, V> t = find(key);
176         return t.value;
177     }
178 
179     /**
180      * Looks for the BinaryTree that contains the specified key as 
181      * its root
182      * @param key is the key that is used to find the BinaryTree
183      * @return the BinaryTree that contains the specified key as 
184      * its root
185      */
186     public BinaryTree<K, V> find(K key) {
187         if (empty()) {
188             return null;
189         } else if (this.key.equals(key)) {
190             return this;
191         } else {
192             BinaryTree<K, V> l = lchild.find(key);
193             if (l != null) {
194                 return l;
195             }
196             BinaryTree<K, V> r = rchild.find(key);
197             if (r != null) {
198                 return r;
199             }
200             return null;
201         }
202     }
203 
204     /**
205      * Determines whether a key is in the BinaryTree
206      * @param key is the key for which is being searched
207      * @return true if the specified key is in the BinaryTree
208      */
209     public boolean member(K key) {
210         if (empty()) {
211             return false;
212         } else if (this.key.equals(key)) {
213             return true;
214         } else {
215             return (lchild.member(key) | rchild.member(key));
216         }
217     }
218 
219     /**
220      * Prints a pair of key and value in the BinaryTree to the output stream
221      */
222     public void visit() {
223         String rep;
224         if (value == null) {
225             rep = "---";
226         } else {
227             rep = value.toString();
228         }
229         String s = "[" + key + ":" + rep + "]";
230         System.out.println(s);
231     }
232 
233     /**
234      * Establishes a pair of key and value as the root in the BinaryTree
235      * @param key is the key of the root
236      * @param value is the value of the root
237      */
238     public void sprout(K key, V value) {
239         this.key = key;
240         this.value = value;
241         this.lchild = new BinaryTree<K, V>();
242         this.rchild = new BinaryTree<K, V>();
243     }
244 
245 }
246