Posted By

shaylenpatel7 on 04/10/15


Tagged

java search tree binary


Versions (?)

Birthday Binary Search Tree


 / Published in: Java
 

This program is about a binary search tree.

  1. import java.io.File;
  2. import java.io.FileReader;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.Scanner;
  8.  
  9. public class BirthdayBinarySearchTree {
  10. private BSTnode root;
  11.  
  12. public static void main(String[] args) throws Exception {
  13. BirthdayBinarySearchTree tree = new BirthdayBinarySearchTree();
  14.  
  15. if (args.length > 0) {
  16. Scanner scanner = new Scanner(new FileReader("birthdays.txt"));
  17. String line;
  18. while (scanner.hasNextLine()) {
  19. line = scanner.nextLine();
  20.  
  21. String[] parts = line.split(" ", 3);
  22. if (3 == parts.length) {
  23. tree.add(parts[2], Integer.valueOf(parts[0]),
  24. Integer.valueOf(parts[1]));
  25. }
  26. }
  27. } else {
  28. tree.add("Test 3,3", 3, 3);
  29. tree.add("Test 1,1 (1)", 1, 1);
  30. tree.add("Test 1,1 (2)", 1, 1);
  31. tree.add("Test 2,2", 2, 2);
  32. tree.add("Test 4,4", 4, 4);
  33.  
  34. if (null != tree.get(5, 5)) {
  35. System.out.println("Error");
  36. }
  37.  
  38. System.out.println("Jan, 1 birthdays");
  39.  
  40. ArrayList<String> names = tree.get(1, 1);
  41. if (null == names) {
  42. System.out.println("Error");
  43. } else {
  44. for (String name : names) {
  45. System.out.println(" - " + name);
  46. }
  47. }
  48. System.out.println();
  49. }
  50.  
  51. System.out.println("List all");
  52. tree.listAll();
  53. System.out.println();
  54.  
  55. System.out.println("List range");
  56. tree.listRange(2, 2, 4, 4);
  57. }
  58.  
  59. public void add(String name, int birthMonth, int birthDay) {
  60. root = addHelper(root, name, new Birthday(birthMonth, birthDay));
  61. }
  62.  
  63. private BSTnode addHelper(BSTnode node, String name, Birthday birthday) {
  64. if (null == node) {
  65. return new BSTnode(name, birthday);
  66. }
  67.  
  68. int compareTo = birthday.compareTo(node.getBirthday());
  69.  
  70. if (compareTo > 0) {
  71. node.right = addHelper(node.getRight(), name, birthday);
  72. } else if (compareTo < 0) {
  73. node.left = addHelper(node.getLeft(), name, birthday);
  74. } else {
  75. node.getNames().add(name);
  76. }
  77.  
  78. return node;
  79. }
  80.  
  81. public void listAll() {
  82. listHelper(iteratorInOrder());
  83. }
  84.  
  85. private void listHelper(Iterator<BSTnode> iterator) {
  86. while (iterator.hasNext()) {
  87. BSTnode node = iterator.next();
  88. StringBuilder sb = new StringBuilder();
  89. sb.append(node.getBirthday()).append("\n");
  90.  
  91. for (String name : node.getNames()) {
  92. sb.append(" - ").append(name).append("\n");
  93. }
  94.  
  95. System.out.print(sb);
  96. }
  97. }
  98.  
  99. public ArrayList<String> get(int birthdayMonth, int birthDay) {
  100. Birthday birthday = new Birthday(birthdayMonth, birthDay);
  101. BSTnode node = root;
  102.  
  103. while (null != node) {
  104. int compareTo = birthday.compareTo(node.getBirthday());
  105.  
  106. if (compareTo > 0) {
  107. node = node.getRight();
  108. } else if (compareTo < 0) {
  109. node = node.getLeft();
  110. } else {
  111. return node.getNames();
  112. }
  113. }
  114.  
  115. return null;
  116. }
  117.  
  118. public void listRange(int startMonth, int startDay, int endMonth, int endDay) {
  119. List<BSTnode> list = new LinkedList<BSTnode>();
  120. rangeIterateHelper(root, list, new Birthday(startMonth, startDay),
  121. new Birthday(endMonth, endDay));
  122. listHelper(list.iterator());
  123. }
  124.  
  125. private void rangeIterateHelper(BSTnode node, List<BSTnode> list,
  126. Birthday min, Birthday max) {
  127. if (node == null) {
  128. return;
  129. }
  130.  
  131. int minCompareTo = min.compareTo(node.getBirthday());
  132. int maxCompareTo = max.compareTo(node.getBirthday());
  133.  
  134. if (minCompareTo < 0) {
  135. rangeIterateHelper(node.getLeft(), list, min, max);
  136. }
  137.  
  138. if ((minCompareTo <= 0) && (maxCompareTo >= 0)) {
  139. list.add(node);
  140. }
  141.  
  142. if (maxCompareTo > 0) {
  143. rangeIterateHelper(node.getRight(), list, min, max);
  144. }
  145. }
  146.  
  147. public Iterator<BSTnode> iteratorInOrder() {
  148. List<BSTnode> list = new LinkedList<BSTnode>();
  149. iterateHelper(list, root);
  150. return list.iterator();
  151. }
  152.  
  153. private void iterateHelper(List<BSTnode> list, BSTnode node) {
  154. if (null != node) {
  155. iterateHelper(list, node.getLeft());
  156. list.add(node);
  157. iterateHelper(list, node.getRight());
  158. }
  159. }
  160.  
  161. private static class BSTnode {
  162. private Birthday birthday;
  163. private ArrayList<String> names = new ArrayList<String>();
  164.  
  165. private BSTnode left;
  166. private BSTnode right;
  167.  
  168. private BSTnode(String name, Birthday birthday) {
  169. this.birthday = birthday;
  170. this.names.add(name);
  171. }
  172.  
  173. private Birthday getBirthday() {
  174. return birthday;
  175. }
  176.  
  177. private ArrayList<String> getNames() {
  178. return names;
  179. }
  180.  
  181. private BSTnode getLeft() {
  182. return left;
  183. }
  184.  
  185. private BSTnode getRight() {
  186. return right;
  187. }
  188. }
  189.  
  190. private static class Birthday implements Comparable<Birthday> {
  191. private int month;
  192. private int day;
  193.  
  194. private Birthday(int month, int day) {
  195. this.month = month;
  196. this.day = day;
  197. }
  198.  
  199. public int compareTo(Birthday that) {
  200. if (this.month < that.month) {
  201. return -1;
  202. }
  203.  
  204. if (this.month > that.month) {
  205. return 1;
  206. }
  207.  
  208. if (this.day < that.day) {
  209. return -1;
  210. }
  211.  
  212. if (this.day > that.day) {
  213. return 1;
  214. }
  215.  
  216. return 0;
  217. }
  218.  
  219. public String toString() {
  220. return "month=" + month + ", day=" + day;
  221. }
  222.  
  223. private int getMonth() {
  224. return month;
  225. }
  226.  
  227. private void setMonth(int month) {
  228. this.month = month;
  229. }
  230.  
  231. private int getDay() {
  232. return day;
  233. }
  234.  
  235. private void setDay(int day) {
  236. this.day = day;
  237. }
  238. }
  239. }

Report this snippet  

You need to login to post a comment.