Advertisement
Guest User

Untitled

a guest
Nov 19th, 2018
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.04 KB | None | 0 0
  1.  
  2. /** binary search tree */
  3.  
  4. package dataStructures;
  5.  
  6. public class BinarySearchTree extends LinkedBinaryTree
  7. implements BSTree
  8. {
  9. // top-level nested class
  10. static class Data
  11. {
  12. // data members
  13. Object element; // element in node
  14. Comparable key; // its key
  15.  
  16. // constructor
  17. Data(Comparable theKey, Object theElement)
  18. {
  19. key = theKey;
  20. element = theElement;
  21. }
  22.  
  23. public String toString()
  24. {return element.toString();}
  25. }
  26.  
  27. /** @return element with specified key
  28. * @return null if no matching element */
  29. public Object get(Object theKey)
  30. {
  31. // pointer p starts at the root and moves through
  32. // the tree looking for an element with key theKey
  33. BinaryTreeNode p = root;
  34. Comparable searchKey = (Comparable) theKey;
  35. while (p != null)
  36. // examine p.element.key
  37. if (searchKey.compareTo(((Data) p.element).key) < 0)
  38. p = p.leftChild;
  39. else
  40. if (searchKey.compareTo(((Data) p.element).key) > 0)
  41. p = p.rightChild;
  42. else // found matching element
  43. return ((Data) p.element).element;
  44.  
  45. // no matching element
  46. return null;
  47. }
  48.  
  49. /** insert an element with the specified key
  50. * overwrite old element if there is already an
  51. * element with the given key
  52. * @return old element (if any) with key theKey */
  53. public Object put(Object theKey, Object theElement)
  54. {
  55. BinaryTreeNode p = root, // search pointer
  56. pp = null; // parent of p
  57. Comparable elementKey = (Comparable) theKey;
  58. // find place to insert theElement
  59. while (p != null)
  60. {// examine p.element.key
  61. pp = p;
  62. // move p to a child
  63. if (elementKey.compareTo(((Data) p.element).key) < 0)
  64. p = p.leftChild;
  65. else if (elementKey.compareTo(((Data) p.element).key) > 0)
  66. p = p.rightChild;
  67. else
  68. {// overwrite element with same key
  69. Object elementToReturn = ((Data) p.element).element;
  70. ((Data) p.element).element = theElement;
  71. return elementToReturn;
  72. }
  73. }
  74.  
  75. // get a node for theElement and attach to pp
  76. BinaryTreeNode r = new BinaryTreeNode
  77. (new Data(elementKey, theElement));
  78. if (root != null)
  79. // the tree is not empty
  80. if (elementKey.compareTo(((Data) pp.element).key) < 0)
  81. pp.leftChild = r;
  82. else
  83. pp.rightChild = r;
  84. else // insertion into empty tree
  85. root = r;
  86. return null;
  87. }
  88.  
  89. /** @return matching element and remove it
  90. * @return null if no matching element */
  91. public Object remove(Object theKey)
  92. {
  93. Comparable searchKey = (Comparable) theKey;
  94.  
  95. // set p to point to node with key searchKey
  96. BinaryTreeNode p = root, // search pointer
  97. pp = null; // parent of p
  98. while (p != null && !((Data) p.element).key.equals(searchKey))
  99. {// move to a child of p
  100. pp = p;
  101. if (searchKey.compareTo(((Data) p.element).key) < 0)
  102. p = p.leftChild;
  103. else
  104. p = p.rightChild;
  105. }
  106.  
  107. if (p == null) // no element with key searchKey
  108. return null;
  109.  
  110. // save element to be removed
  111. Object theElement = ((Data) p.element).element;
  112.  
  113. // restructure tree
  114. // handle case when p has two children
  115. if (p.leftChild != null && p.rightChild != null)
  116. {// two children
  117. // convert to zero or one child case
  118. // find element with largest key in left subtree of p
  119. BinaryTreeNode s = p.leftChild,
  120. ps = p; // parent of s
  121. while (s.rightChild != null)
  122. {// move to larger element
  123. ps = s;
  124. s = s.rightChild;
  125. }
  126.  
  127. // move largest element from s to p
  128. p.element = s.element;
  129. p = s;
  130. pp = ps;
  131. }
  132.  
  133. // p has at most one child, save this child in c
  134. BinaryTreeNode c;
  135. if (p.leftChild == null)
  136. c = p.rightChild;
  137. else
  138. c = p.leftChild;
  139.  
  140. // remove node p
  141. if (p == root) root = c;
  142. else
  143. {// is p left or right child of pp?
  144. if (p == pp.leftChild)
  145. pp.leftChild = c;
  146. else
  147. pp.rightChild = c;
  148. }
  149.  
  150. return theElement;
  151. }
  152.  
  153. /** output elements in ascending order of key */
  154. public void ascend()
  155. {inOrderOutput();}
  156.  
  157. // test binary search tree class
  158. public static void main(String [] args)
  159. {
  160. BinarySearchTree y = new BinarySearchTree();
  161.  
  162. // insert a few elements
  163. y.put(new Integer(1), new Character('a'));
  164. y.put(new Integer(6), new Character('c'));
  165. y.put(new Integer(4), new Character('b'));
  166. y.put(new Integer(8), new Character('d'));
  167. System.out.println("Elements in ascending order are");
  168. y.ascend();
  169. System.out.println();
  170.  
  171. // remove an element
  172. System.out.println("Removed element " + y.remove(new Integer(4)) +
  173. " with key 4");
  174. System.out.println("Elements in ascending order are");
  175. y.ascend();
  176. System.out.println();
  177.  
  178. // remove another element
  179. System.out.println("Removed element " + y.remove(new Integer(8)) +
  180. " with key 8");
  181. System.out.println("Elements in ascending order are");
  182. y.ascend();
  183. System.out.println();
  184.  
  185. // remove yet another element
  186. System.out.println("Removed element " + y.remove(new Integer(6)) +
  187. " with key 6");
  188. System.out.println("Elements in ascending order are");
  189. y.ascend();
  190. System.out.println();
  191.  
  192. // try to remove a nonexistent element
  193. System.out.println("Removed element " + y.remove(new Integer(6)) +
  194. " with key 6");
  195. System.out.println("Elements in ascending order are");
  196. y.ascend();
  197. System.out.println();
  198. }
  199. }
  200.  
  201. --------
  202. Binary Search Tree With Range (not finished yet, barely started)
  203.  
  204. package dataStructures;
  205.  
  206. public class BinarySearchTreeWithOutputInRange extends BinarySearchTree {
  207.  
  208. Comparable key;
  209. Object element;
  210.  
  211. //constructor
  212. BinarySearchTreeWithOutputInRange()
  213. {
  214. super();
  215. }
  216.  
  217. //public method outputInRange
  218. public void outputInRange(Comparable theLow, Comparable theHigh)
  219. {
  220. // code to be inserted
  221. }
  222.  
  223.  
  224. public static void main(String args[])
  225. {
  226. BinarySearchTreeWithOutputInRange x =
  227. new BinarySearchTreeWithOutputInRange();
  228. // insert a few elements
  229. x.put(new Integer(55), new Character('a'));
  230. x.put(new Integer(10), new Character('b'));
  231.  
  232. System.out.println("\nElements in ascending order are");
  233. x.ascend();
  234. System.out.println("");
  235. x.outputInRange(20, 70);
  236.  
  237.  
  238.  
  239. }
  240. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement