Question

In: Computer Science

In Java For this assignment you will implement two methods, find() and replace() relating to Binary...

In Java

For this assignment you will implement two methods, find() and replace() relating to Binary Search Trees. These methods are both to be recursive functions. The signatures for those functions must be:

 /* This method takes a tree node and a key as an argument and returns the tree node if the key is found and returns null if the key is not found. */ 
BST find(BST T, char key)

/* This method takes a tree node and a key as an argument and inserts the tree node if the key is already in the tree it does not insert the node. It returns the new tree. */
BST insert(BST T, char key)

Also, for this assignment you are to implement the preOrder(), inOrder(), and postOrder() tree traversal methods. These methods are also to be recursive functions.

All five of these methods are detailed and discussed in the lecture notes and videos. You are allowed to use the pseudo-code and any associated code described in the lecture and videos. However, you are not required for any of it.

The input for this program will be from the keyboard and accept single-character keys, labeled 'A' - 'Z'.

Programming Notes & Rules:

  1. You can not delete any code in the BST class. But you can add code to the BST class if you wish.
  2. All five methods must be recursive. Zero credit will be given for any non-recursive method even if it works correctly.
  3. Do not assume any maximum length for any input string.
  4. You need not test for the null or empty string ("") case,
  5. You are not allowed to add any arrays or ArrayLists or any Java built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues, Deques, Trees, Graphs, Heaps, etc. Or add any class that inherits any of those ADTs.
  6. For your node and list class, you can use the code that was used in the book, video, and lecture notes related to the node and lists class examples.
  7. You are not allowed to use Java Generics.
  8. If hard-coding detected in any part of your solution your score will be zero for the whole assignment.

Starter Code:

import java.util.Scanner;  // Import the Scanner class

public class BST {
  
  public char key;
  public BST  left;
  public BST  right;

  public BST(char c) {
    key   = c;
    left  = null;
    right = null;
  }
  
  public static BST find(BST T, char key) {
  // put your solution here
  }

  public static BST insert(BST T, char key) {
  //  put your solution here
  }
    
  public static void preOrder(BST T) {
  //  put your solution here
  }
  
  public static void inOrder(BST T) {
  //  put your solution here 
  }
  
  public static void postOrder(BST T) {
  //  put your solution here
  }
  
  public static void main(String[] args) {
     Scanner input = new Scanner(System.in);
     BST t = null;
     String stream = input.nextLine();
     for (int i = 0; i < stream.length(); i++)
       t = insert(t, stream.charAt(i));
     System.out.print("Preorder: ");
     preOrder(t);
     System.out.println();
     System.out.print("Inorder: ");
     inOrder(t);
     System.out.println();
     System.out.print("Postorder: ");
     postOrder(t);
     System.out.println();
     System.out.println("Enter a character to search for: ");
     char c = input.nextLine().charAt(0);
     if (find(t, c) == null)
       System.out.println("The character " + "'" + c + "' was not found.");
     else
       System.out.println("The character " + "'" + c + "' was found.");
   }

Solutions

Expert Solution

WHOLE CODE WITH IMPLEMENTED ABOVE METHODS :

import java.util.Scanner;  // Import the Scanner class

public class BST {

   public char key;
   public BST  left;
   public BST  right;

   public BST(char c) {
      key   = c;
      left  = null;
      right = null;
   }


   public static BST find(BST T, char key) {

      if(T==null)
         return null;

      if(T.key==key)
         return T;

      else if(key>T.key){
         return find(T.right,key);
      }

      else{
         return find(T.left,key);
      }

   }


   public static BST insert(BST T, char key) {

      if(T==null){
         BST newNode = new BST(key);
         return newNode;
      }

      if(T.key>=key){
         T.left = insert(T.left,key);
      }

      else{
         T.right=insert(T.right,key);
      }

      return T;
   }


   public static void preOrder(BST T) {
      if(T==null)
         return;

      System.out.print(T.key+" ");
      preOrder(T.left);
      preOrder(T.right);
   }


   public static void inOrder(BST T) {
      if(T==null)
         return;

      preOrder(T.left);
      System.out.print(T.key+" ");
      preOrder(T.right);

   }


   public static void postOrder(BST T) {
      if(T==null)
         return;

      preOrder(T.left);
      preOrder(T.right);
      System.out.print(T.key+" ");

   }


   public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      BST t = null;
      String stream = input.nextLine();
      for (int i = 0; i < stream.length(); i++)
         t = insert(t, stream.charAt(i));
      System.out.print("Preorder: ");
      preOrder(t);
      System.out.println();
      System.out.print("Inorder: ");
      inOrder(t);
      System.out.println();
      System.out.print("Postorder: ");
      postOrder(t);
      System.out.println();
      System.out.println("Enter a character to search for: ");
      char c = input.nextLine().charAt(0);
      if (find(t, c) == null)
         System.out.println("The character " + "'" + c + "' was not found.");
      else
         System.out.println("The character " + "'" + c + "' was found.");
   }



}


EXAMPLE :


Related Solutions

Implement two methods, find() and replace() relating to Binary Search Trees. Both of these methods must...
Implement two methods, find() and replace() relating to Binary Search Trees. Both of these methods must be recursive functions. The signatures for the functions must be: /* This method takes a tree node and a key as an argument and returns the tree node if the key is found and returns null if the key is not found. */ BST find(BST T, char key) /* This method takes a tree node and a key as an argument and inserts the...
Overview In this assignment you are required to implement binary code comparator using Xilinx that it...
Overview In this assignment you are required to implement binary code comparator using Xilinx that it is compatible with the MXK Seven Segment Displays. You will draw your digital logic circuit using Xilinx and then simulate it to verify the functionality of your design. Software Requirements ? Xilinx ISE 10.1 or higher Specifications Binary Code Comparator The binary code comparator is to be implemented and made compatible with the seven 7-segment displays of the board. Represent the first five digits...
Please do this in java program. In this assignment you are required to implement the Producer...
Please do this in java program. In this assignment you are required to implement the Producer Consumer Problem . Assume that there is only one Producer and there is only one Consumer. 1. The problem you will be solving is the bounded-buffer producer-consumer problem. You are required to implement this assignment in Java This buffer can hold a fixed number of items. This buffer needs to be a first-in first-out (FIFO) buffer. You should implement this as a Circular Buffer...
0. Introduction. In this assignment you will implement a stack as a Java class, using a...
0. Introduction. In this assignment you will implement a stack as a Java class, using a linked list of nodes. Unlike the stack discussed in the lectures, however, your stack will be designed to efficiently handle repeated pushes of the same element. This shows that there are often many different ways to design the same data structure, and that a data structure should be designed for an anticipated pattern of use. 1. Theory. The most obvious way to represent a...
JAVA: (Find yourself in PI) In this assignment you will find a numeric string (if it...
JAVA: (Find yourself in PI) In this assignment you will find a numeric string (if it exists) within a file containing the first 1 million characters of the decimal expansion of PI. The numeric string in question is a 6 character string representing your birth date. E.g., if your birth date is January 1, 1984, then the string is 010184. The file containing the first 1 million characters of the decimal expansion of PI is named pidigits.txt and is available...
JAVA the task is to implement the missing methods in the LinkedIntSet class. Each method you...
JAVA the task is to implement the missing methods in the LinkedIntSet class. Each method you must write has comments describing how it should behave. You may not add any new fields to the LinkedIntSet class and you may only add new code inside the bodies of the 5 methods you are asked to write. You may also write new private helper methods. However, you may not change any method headers, you may not change any code outside of the...
Use Java programming to implement the following: Implement the following methods in the UnorderedList class for...
Use Java programming to implement the following: Implement the following methods in the UnorderedList class for managing a singly linked list that cannot contain duplicates. Default constructor Create an empty list i.e., head is null. boolean insert(int data) Insert the given data into the end of the list. If the insertion is successful, the function returns true; otherwise, returns false. boolean delete(int data) Delete the node that contains the given data from the list. If the deletion is successful, the...
For this computer assignment, you are to write and implement an interactive C++ program to find...
For this computer assignment, you are to write and implement an interactive C++ program to find and print all prime numbers, which are less than or equal to a given value of n, using the algorithm known as the Sieve of Eratosthenes. A prime number p is an integer greater than 1 that is divisible only by 1 and p (itself). The algorithm begins by initializing a set container to contain all the integers in the range 2 to n....
Overview For this assignment, design and implement the methods for a class that can be used...
Overview For this assignment, design and implement the methods for a class that can be used to represent a quadratic equation. int main() has already been written for this assignment. It is available for download from Blackboard or by using the following link: http://faculty.cs.niu.edu/~byrnes/csci240/pgms/240pgm8.cpp All that needs to be done for this assignment is to add the class definition and method implementation to the above CPP file. The Quadratic class Data Members The class contains three data members: an integer...
JAVA WITH NO IMPORTS Method changeWords executes a find and replace like you would with ctrl+f...
JAVA WITH NO IMPORTS Method changeWords executes a find and replace like you would with ctrl+f            or command+f on here            The first value provided is the text that you search            Turn the text into an array of strings            find the string that is sent in the second position (find) and            replace it with the           changeWords("never have I ever", "ever", "cheated") returns ["never",...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT