for java You will need to implement a basic BST with the following method. BST()

Question

for java

You will need to implement a basic BST with the following method.

BST() //constructor to set the root to null

isEmpty() : boolean

insert(T t):void // puts the node t of type <T> into the BST

search(T target):<T> Returns a reference variable to Target, if target is found. Returns null if not found.

print(): void (or returns String if you prefer). This prints the BST in order. If you add strings, it will return them in compareTo() order.

Get your program working. Test it with String data type.

After you get it working with strings create a wordCount class. The program you actually turn in should use the WordCount class.

The WordCount class has two fields. The first field is a string. The second field is an integer that counts how often a given word has been encountered. WordCount should have the following methods

WordCount(String word) This creates the node by saving the word into the String field and setting the counter to 1. The string should be converted to lower case.

getCount:int returns the count field

increment():void Adds 1 to the count field

compareTo(WordCount other):int Returns a comparison of the Strings. The count is ignored.

toString() Returns a nicely formatted string of both fields.

Your program should read from a file called "input.txt" It should entire lines from the file and use the following to split the line. If the line is empty, do not put anything in the table.

String[] words = line.split("[^A-Za-z']+");

The line should split each line into individual words. For each word, you will need to instantiate a WordClass object. Then you will need to search the BST to see if new object is in the tree. If the item is in the tree, increment the object that is in the tree (not the temporary WordCount object that you created) If the item is not in the tree then insert it.

After the entire file is read, print the list of words. Here is an example.

input.txt:

Peter Piper picked a peck of pickled peppers.
A peck of pickled peppers, Peter Piper picked.
If Peter Piper picked a peck of pickled pepper,
where is the peck of picked peppers that Peter Piper Picked?

Output:

a (3)
if (1)
is (1)
of (4)
peck (4)
pepper (1)
peppers (3)
peter (4)
picked (5)
pickled (3)
piper (4)
that (1)
the (1)
where (1)

Explanation / Answer

import tester.*;

interface ib {

ib addElt (int elt);

ib remElt (int elt);

int size ();

boolean hasElt (int elt);

int largestElt();

ib remParent(ib sibling);

ib mergeToRemoveParent(ib sibling);
}

class mt implements ib {
mt() {}


public int size () { return 0; }


public ib addElt (int elt) {
    return new databs(elt, new mt(), new mt());
}

public ib remElt (int elt) { return this; }

public boolean hasElt (int elt) { return false; }

public int largestElt () {
    throw new RuntimeException("shouldn't call largestElt on mt") ;
}


public ib remParent(ib rightsibling) {
    return rightsibling;
}

public ib mergeToRemoveParent(ib leftsibling) {
    return leftsibling;
}
}

class databs implements ib {
int data;
ib left;
ib right;

databs(int data, ib left, ib right) {
    this.data = data;
    this.left = left;
    this.right = right;
}


public int size() {
    return 1 + this.left.size() + this.right.size();
}


public ib addElt (int elt) {
    if (elt == this.data)
      return this; // not storing duplicate values
    else if (elt < this.data)
      return new databs (this.data,
                          this.left.addElt(elt),
                          this.right);
    else // elt > this.data
      return new databs (this.data,
                          this.left,
                          this.right.addElt(elt));
}


public int largestElt() {
    if (this.right instanceof mt)
      return this.data;
    else return this.right.largestElt();
}


public boolean hasElt (int elt) {
    if (elt == this.data)
      return true;
    else if (elt < this.data)
      return this.left.hasElt(elt);
    else // elt > this.data
      return this.right.hasElt(elt);
}

public ib remElt (int elt) {
   if (elt == this.data) {
   
       return this.left.remParent(this.right);
   }
   else if (elt < this.data)
       return new databs(this.data, this.left.remElt(elt), this.right);
   else // (elt > this.data)
      return new databs(this.data, this.left, this.right.remElt(elt)) ;
}


public ib remParent(ib rightSibling) {
    return rightSibling.mergeToRemoveParent(this);
}


    int newRoot = leftSibling.largestElt();
    return new databs(newRoot,
                       leftSibling.remElt(newRoot),
                       this);
}
}

class Examples {
Examples(){}

ib b1 = new databs (5, new mt(), new mt());
ib b2 = b1.addElt(3).addElt(4).addElt(8).addElt(7);
ib b2no4 = b1.addElt(3).addElt(8).addElt(7);
ib b2no8 = b1.addElt(3).addElt(4).addElt(7);
ib b2rem5 = new databs(4, new mt(), new mt()).addElt(3).addElt(8).addElt(7);

boolean test1 (Tester t) {
    return t.checkExpect(b2.size(), 5);
}


boolean test2 (Tester t) {
    return t.checkExpect(b1.addElt(7).size(), 2);
}
  

boolean test3 (Tester t) {
    return t.checkExpect(b1.addElt(5).size(), 1);
}


boolean test4 (Tester t) {
    return t.checkExpect(b2.remElt(4), b2no4);
}


boolean test5 (Tester t) {
    return t.checkExpect(b2.remElt(8), b2no8);
}

boolean test6 (Tester t) {
    return t.checkExpect(b2.remElt(5), b2rem5);
}

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.