SHARE
TWEET

Untitled

a guest Nov 21st, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. /**
  5.  * A program that creates a binary search tree object
  6.  * Daniel Scarbrough
  7.  * Version 1.0
  8.  */
  9. public class BinarySearchTree <E extends Comparable<E>> {
  10.     private Node root;
  11.     private static String filename = "English.lex";     //holds file name in field
  12.     private int counter;        //counts how many nodes are present
  13.  
  14.     public BinarySearchTree() {
  15.         root = null;
  16.         counter = 0;
  17.     }
  18.  
  19.  
  20.     public  void insert(E object) {
  21.         counter++;
  22.         Node newNode = new Node(object);
  23.         if (root == null) {
  24.             root = newNode;
  25.             return;
  26.         }
  27.         Node current = root;
  28.         Node parent = null;
  29.         while (true) {  //goes until return statement
  30.             parent = current;
  31.             if (object.compareTo(current.data) < 0) {
  32.                 current = current.left;
  33.                 if (current == null) {
  34.                     parent.left = newNode;
  35.                     return;
  36.                 }
  37.             } else {
  38.                 current = current.right;
  39.                 if (current == null) {
  40.                     parent.right = newNode;
  41.                     return;
  42.                 }
  43.             }
  44.         }
  45.     }
  46.  
  47.     /**
  48.      * checks the tree to see if it contains the value
  49.      * @param value value to be checked
  50.      * @return true if value is in tree, false if not
  51.      */
  52.     public boolean has (E value){
  53.         Node current = root;
  54.         while (current!=null){
  55.             if(current.data.compareTo(value)>0){
  56.                 current=current.left;
  57.             }else if (current.data.compareTo(value)<0){
  58.                 current=current.right;
  59.             }
  60.             else if (current.data.equals(value)) return true;
  61. }
  62.         return false;
  63.     }
  64.  
  65.     /**
  66.      *finds the minimum value in the tree
  67.      * @return the minimum value
  68.      */
  69.     public E findMin(){
  70.         Node current = root;
  71.         if (root == null)
  72.             return null;
  73.         while (current.left != null) {
  74.             current = current.left;
  75.         }
  76.         return current.data;
  77.     }
  78.  
  79.     /**
  80.      *finds the maximum value in the tree
  81.      * @return the data of the max value
  82.      */
  83.     public E findMax(){
  84.         Node current = root;
  85.         if (root == null)
  86.             return null;
  87.         while (current.right != null) {
  88.             current = current.right;
  89.         }
  90.         return current.data;
  91.     }
  92.  
  93.     /**
  94.      * get the size of the list
  95.      * @return the size of the list
  96.      */
  97.     public int getSize(){
  98.         return counter;
  99.     }
  100.  
  101.     /**
  102.      * private method to help test tree
  103.      * @return a string with root, rootleft and rootright
  104.      */
  105.     private String printTest(){
  106.         String str = " ";
  107.         str+= "Root: "  +root.data;
  108.         str += ":rootL: " +root.left.data;
  109.         str += ":rootR: " +root.right.data;
  110.         return str;
  111.     }
  112.  
  113.     /**
  114.      *finds the next value after the given value
  115.      * @param value to find the succesor of
  116.      * @return data of successor
  117.      */
  118.     public E findSuccessor(E value) {       //mostly identical to findpredecessor, but uses right child
  119.         Node current = root;
  120.         if (root == null)
  121.             return null;
  122.         else if (current.data.equals(value) || has(value) == false)
  123.             return null;
  124.         else {
  125.             if (current.right != null) {
  126.                 current = current.right;
  127.             } else
  128.                 return null;
  129.             if (current != null) {
  130.                 while (current.left != null) {
  131.                     current = current.left;
  132.                 }
  133.             }
  134.         }
  135.         return current.data;
  136.     }
  137.  
  138.     /**
  139.      *finds the value immediately before given value
  140.      * @param value value to find predecessor of
  141.      * @return value of predecessor
  142.      */
  143.     public E findPredecessor(E value) {
  144.         Node current = root;
  145.         if (root == null)
  146.             return null;
  147.         else if (current.data.equals(value) || has(value) == false)
  148.             return null;
  149.         else {
  150.             if (current.left != null) {
  151.                 current = current.left;
  152.             } else
  153.                 return null;
  154.             if (current != null) {
  155.                 while (current.right != null) {
  156.                     current = current.right;
  157.                 }
  158.             }
  159.         }
  160.         return current.data;
  161.     }
  162.  
  163.  
  164.  
  165.  
  166.     /**
  167.      *Main method
  168.      */
  169.     public static void main(String[] args) {
  170.         BinarySearchTree<String> testTree = new BinarySearchTree<>();
  171.         ArrayList<String> arrayList = new ArrayList<>();        //creates an arrayList that will first hold all elements
  172.         int numWords = 0;       //holds the number of words transferred from the file
  173.         try {      //try catch block to catch filenotfound exception
  174.             Scanner scanner = new Scanner(new File(filename));
  175.             //loops through and adds all elements of file to arrayList
  176.             while (scanner.hasNextLine()) {
  177.                 arrayList.add(scanner.nextLine());      //adds line of the file to a new spot in the arrayList
  178.                 numWords++;     //iterates the number of words so we know how many elements there are
  179.             }
  180.             Collections.shuffle(arrayList);     //shuffles the arrayList
  181.  
  182.              for(int i = 0; i < arrayList.size(); i++){ //copies all elements from arrayList to the binaryTree.
  183.                  testTree.insert(arrayList.get(i));
  184.              }
  185.  
  186.             Scanner keyboard = new Scanner(System.in); //holds user input for loop
  187.             boolean stopOrNot = false;      //holds condition for while loop
  188.  
  189.             System.out.println("Testing binary search tree");
  190.             System.out.println("loaded " +filename + "( " +numWords + " words from " +testTree.findMin() + " to " + testTree.findMax()+")");
  191.             System.out.println("Please enter a word, or hit enter to quit");
  192.  
  193.             System.out.println(testTree.printTest());
  194.  
  195.  
  196.             do {
  197.  
  198.                 String str = keyboard.nextLine();
  199.                 if (str.equals("")) {                   //if user input is just "enter" then will close program
  200.                     System.out.println("Goodbye!");
  201.                     stopOrNot = true;
  202.                 } else {
  203.                     if (testTree.has(str)) {
  204.                         System.out.println(str + " is a valid word!");
  205.                     } else {
  206.                         System.out.println(str + " is NOT a valid word!");
  207.                     }
  208.                 }
  209.  
  210.  
  211.             }
  212.             while (!stopOrNot);
  213.  
  214.  
  215.         }
  216.         catch(FileNotFoundException ex){
  217.             System.out.println("File not found: Please try again");
  218.         }
  219.     }
  220.  
  221.     /**
  222.      * private Node class used to make each node object
  223.      */
  224.     private class Node{
  225.         private E data;         //holds the nodes Data
  226.         private Node left;      //holds Nodes pointer to left node (less)
  227.         private Node right;     //holds Nodes pointer to right node (bigger)
  228.  
  229.         /**
  230.          * @param data  data that the node will hold
  231.  
  232.          */
  233.         private Node(E data) {     //constructor to set node data
  234.             this.data = data;
  235.             this.left = null;
  236.             this.right = null;
  237.         }
  238.  
  239.  
  240.  
  241.         /**
  242.          * @param node node whos data want printed
  243.          * @return returns data in ()
  244.          */
  245.         private String toString(Node node) {
  246.             return ("(" + node.data + ")");
  247.         }
  248.     }
  249.  
  250. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top