Homework SourseNeed code in Java Need help writing the code for unbalanced
Need code in Java.
Need help writing the code for unbalanced() binary search tree.
-------------------------------
Here\'s my balanced.
public void balance() { //recursivelyAdd
balance(0, list.size()); //Runs this method selecting the parameters at index 0 and the size of the list.
for(int j = 0; j < list.size(); j++) //Runs a for loop to go through the elements in the array list.
{
if(!contains(list.get(j))) //If the BST tree does not contain the element specified, this if statement runs.
{
wordList.add(list.get(j)); // Adds the word to the BST tree.
indexNumber++; //Increments the indexNumber due to the adding.
//System.out.println(indexNumber + \" : \" + list.get(j)); //Prints out the indexNumber of the element and the element itself. (Element in this case is the word)
}
}
}
public void balance(int start, int end) { //This method recursively adds the halves of the array list to the BST tree.
if (start >= end) //
return;
int mid = start + (end - start) / 2; //Halves the array list tree for the first time or again(Depending if it is the first time going through this method).
wordList.add(list.get(mid)); //Adds the specified halved element to the BST tree.
indexNumber++; //Increments the indexNumber due to the adding.
//System.out.println(indexNumber + \" : \" + list.get(mid)); //Prints out the indexNumber of the element and the element itself. (Element in this case is the word)
balance(start + 1, mid-1); // recursively adding the words in the middle of the left
balance(mid+1, end - 1); // recursively adding the words in the middle of the right
}
Solution
BinartSearchTree.java
public class BinarySearchTree {
public BinarySearchTree() {
root = null;
}
public void add(Comparable x) {
root = add(x, root);
}
public void delete(Comparable x) {
root = delete(x, root);
}
public void removeMin() {
root = removeMin(root);
}
public Comparable findMin() {
return elementAt(findMin(root));
}
public Comparable findMax() {
return elementAt(findMax(root));
}
public Comparable find(Comparable x) {
return elementAt(find(x, root));
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
private Comparable elementAt(BinaryNode t) {
return t == null ? null : t.element;
}
protected BinaryNode add(Comparable x, BinaryNode t) {
if (t == null) {
t = new BinaryNode(x);
} else if (x.compareTo(t.element) < 0) {
t.lft = add(x, t.lft);
} else if (x.compareTo(t.element) > 0) {
t.rgt = add(x, t.rgt);
} else {
throw new DuplicateItemException(x.toString());
}
return t;
}
protected BinaryNode delete(Comparable x, BinaryNode t) {
if (t == null) {
throw new ItemNotFoundException(x.toString());
}
if (x.compareTo(t.element) < 0) {
t.lft = delete(x, t.lft);
} else if (x.compareTo(t.element) > 0) {
t.rgt = delete(x, t.rgt);
} else if (t.lft != null && t.rgt != null)
{
t.element = findMin(t.rgt).element;
t.rgt = removeMin(t.rgt);
} else {
t = (t.lft != null) ? t.lft : t.rgt;
}
return t;
}
protected BinaryNode removeMin(BinaryNode t) {
if (t == null) {
throw new ItemNotFoundException();
} else if (t.lft != null) {
t.lft = removeMin(t.lft);
return t;
} else {
return t.rgt;
}
}
protected BinaryNode findMin(BinaryNode t) {
if (t != null) {
while (t.lft != null) {
t = t.lft;
}
}
return t;
}
private BinaryNode findMax(BinaryNode t) {
if (t != null) {
while (t.rgt != null) {
t = t.rgt;
}
}
return t;
}
private BinaryNode find(Comparable x, BinaryNode t) {
while (t != null) {
if (x.compareTo(t.element) < 0) {
t = t.lft;
} else if (x.compareTo(t.element) > 0) {
t = t.rgt;
} else {
return t;
}
}
return null;
}
protected BinaryNode root;
public static void main(String[] args) {
BinarySearchTree t = new BinarySearchTree();
final int NUMS = 4000;
final int GAP = 37;
System.out.println(\"Checking... (no more output means success)\");
for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
t.add(new Integer(i));
}
for (int i = 1; i < NUMS; i += 2) {
t.delete(new Integer(i));
}
if (((Integer) (t.findMin())).intValue() != 2
|| ((Integer) (t.findMax())).intValue() != NUMS - 2) {
System.out.println(\"FindMin or FindMax error!\");
}
for (int i = 2; i < NUMS; i += 2) {
if (((Integer) (t.find(new Integer(i)))).intValue() != i) {
System.out.println(\"Find error1!\");
}
}
for (int i = 1; i < NUMS; i += 2) {
if (t.find(new Integer(i)) != null) {
System.out.println(\"Find error2!\");
}
}
}
}
class BinaryNode {
BinaryNode(Comparable theElement) {
element = theElement;
lft = rgt = null;
}
Comparable element;
BinaryNode lft;
BinaryNode rgt;
}
DuplicateItemException.java
public class DuplicateItemException extends RuntimeException {
public DuplicateItemException( ) {
super( );
}
public DuplicateItemException( String message ) {
super( message );
}
}
ItemNotFoundException.java
public class ItemNotFoundException extends RuntimeException {
public ItemNotFoundException( ) {
super( );
}
public ItemNotFoundException( String message ) {
super( message );
}
}
