1 /*
  2  *Binarytree.java of trees package
  3  */
  4 /**
  5  * BinaryTreeClass
  6  */
  7 package trees;
  8 
  9 /**
 10  *
 11  * @author sjenks
 12  */
 13 public class BinaryTree<K, V> implements BinaryTreeADT<K, V> {
 14 
 15     private K key;
 16     private V value;
 17     private BinaryTree<K, V> lchild;
 18     private BinaryTree<K, V> rchild;
 19 
 20     /**
 21      * Creates a new BinaryTree instance Sets key to null
 22      */
 23     public BinaryTree() {
 24         key = null;
 25     }
 26 
 27     /**
 28      * @return the value of a node on the tree
 29      */
 30     public V value() {
 31         return value;
 32     }
 33 
 34     /**
 35      * Creates new V value instance
 36      *
 37      * @param value for the node of the tree
 38      */
 39     public void setValue(V value) {
 40         this.value = value;
 41     }
 42 
 43     /**
 44      * Checks to see if a node is empty in the tree
 45      *
 46      * @return key which indicates the name given to the node.
 47      */
 48 
 49     public boolean empty() {
 50         return key == null;
 51     }
 52 
 53     /**
 54      * Computes the height of the tree
 55      *
 56      * @return height which is the position of the max value of one of the
 57      * descendants plus one.
 58      */
 59     public int height() {
 60         if (empty()) {
 61             return 0;
 62         } else {
 63             return 1 + max(lchild.height(), rchild.height());
 64         }
 65     }
 66 
 67     /**
 68      * Determines which child has the highest value Useful for determining the
 69      * height of the tree.
 70      *
 71      * @param a is one of the values to be compared
 72      * @param b is the other value to be compared
 73      * @return the node that has the greater value associated with it.
 74      */
 75     private int max(int a, int b) {
 76         if (a > b) {
 77             return a;
 78         } else {
 79             return b;
 80         }
 81     }
 82 
 83     /**
 84      * Sets up the method to order the nodes in a preorder fashion the order is
 85      * visit the node, go to the left and then to the right
 86      */
 87     public void preorder() {
 88         if (!empty()) {
 89             visit();
 90             lchild.preorder();
 91             rchild.preorder();
 92         }
 93     }
 94 
 95     /**
 96      * Sets up the method to order the nodes in a inorder fashion the order is
 97      * go to the left, visit the node, and then to the right
 98      */
 99     public void inorder() {
100         if (!empty()) {
101             lchild.inorder();
102             visit();
103             rchild.inorder();
104         }
105     }
106 
107     /**
108      * Sets up the method to order the nodes in a postorder fashion the order is
109      * go to the left then the right, and then visit the node
110      */
111     public void postorder() {
112         if (!empty()) {
113             lchild.postorder();
114             rchild.postorder();
115             visit();
116         }
117     }
118 
119     /**
120      * orders the nodes so it forms a binary search tree
121      *
122      * @param key is what the node is called
123      * @param value is the value that the search tree uses to make the BST
124      * @throws BinaryTreeCreationException just in case the data didn't support
125      * making a BST
126      */
127     public void addST(K key, V value) throws BinaryTreeCreationException {
128         if (empty()) {
129             sprout(key, value);
130         } else {
131             Comparable cey = (Comparable) key;
132             Comparable t = (Comparable) this.key;
133             if (cey.compareTo(t) < 0) {
134                 lchild.addST(key, value);
135             } else if (cey.compareTo(t) > 0) {
136                 rchild.addST(key, value);
137             } else {
138                 throw new BinaryTreeCreationException("### can't have equality in bst");
139             }
140         }
141     }
142 
143     /**
144      * orders the nodes so it forms a tree with random connections
145      *
146      * @param key jus the name of the node given
147      * @param value the actual value that the node has
148      */
149     public void addND(K key, V value) {
150         if (empty()) {
151             sprout(key, value);
152         } else if (Math.random() < 0.5) {
153             lchild.addND(key, value);
154         } else {
155             rchild.addND(key, value);
156         }
157     }
158 
159     /**
160      * This allows a person to make their own BST
161      *
162      * @param key name of the node
163      * @param value value of the node that you are giving it
164      * @param dir indicates to the left or right of a node
165      * @throws BinaryTreeCreationException just in case the data does not
166      * support a BST construction
167      */
168     public void addLR(K key, V value, String dir) throws BinaryTreeCreationException {
169         try {
170             if (dir.equals("")) {
171                 sprout(key, value);
172             } else if (dir.substring(0, 1).equalsIgnoreCase("L")) {
173                 lchild.addLR(key, value, dir.substring(1));
174             } else if (dir.substring(0, 1).equalsIgnoreCase("R")) {
175                 rchild.addLR(key, value, dir.substring(1));
176             } else {
177                 throw new BinaryTreeCreationException("### strange directional indicator: " + dir.substring(0, 1));
178             }
179         } catch (BinaryTreeCreationException e) {
180             throw new BinaryTreeCreationException("### no such location in the tree");
181         }
182     }
183 
184     /**
185      * gets the value of the node by looking up the name
186      *
187      * @param key is the name of the node
188      * @return value of the given node from the parameter
189      */
190     public V get(K key) {
191         BinaryTree<K, V> t = find(key);
192         return t.value;
193     }
194 
195     /**
196      * finds a node in the tree
197      *
198      * @param key is the name of the node
199      * @return returns node or null
200      */
201     public BinaryTree<K, V> find(K key) {
202         if (empty()) {
203             return null;
204         } else if (this.key.equals(key)) {
205             return this;
206         } else {
207             BinaryTree<K, V> l = lchild.find(key);
208             if (l != null) {
209                 return l;
210             }
211             BinaryTree<K, V> r = rchild.find(key);
212             if (r != null) {
213                 return r;
214             }
215             return null;
216         }
217     }
218 
219     /**
220      * sees if a node is even in the tree
221      *
222      * @param key name of the node
223      * @return true or false
224      */
225     public boolean member(K key) {
226         if (empty()) {
227             return false;
228         } else if (this.key.equals(key)) {
229             return true;
230         } else {
231             return (lchild.member(key) | rchild.member(key));
232         }
233     }
234 
235     /**
236      * This method is to display a node that is either empty or has a value
237      */
238     public void visit() {
239         String rep;
240         if (value == null) {
241             rep = "---";
242         } else {
243             rep = value.toString();
244         }
245         String s = "[" + key + ":" + rep + "]";
246         System.out.println(s);
247     }
248 
249     /**
250      * to make a new node
251      *
252      * @param key name of the node
253      * @param value value associated with the node
254      */
255     public void sprout(K key, V value) {
256         this.key = key;
257         this.value = value;
258         this.lchild = new BinaryTree<K, V>();
259         this.rchild = new BinaryTree<K, V>();
260     }
261 
262 }
263