aspose file tools*
The moose likes Beginning Java and the fly likes BST problem (Online waiting) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "BST problem (Online waiting)" Watch "BST problem (Online waiting)" New topic
Author

BST problem (Online waiting)

hong Li
Greenhorn

Joined: May 15, 2008
Posts: 4
This is my assignemt, I passed all except one, I have been fixing for ages still cant fix, please help. it's due tomorrow


Due Date: Friday May 16th
Submission Instructions: Submit your files via Moodle
What to Submit: MyBST.java file

For this assignment you are required to implement a binary search tree, called
MyBST.java which implements the BST.java interface. Your tree must allow
duplicates to be stored and to this end each node in the tree has a counter that
represents the number of copies of each number (just as in the linked list you
implemented for the last assignment).
Use the BSTNode class to represent the nodes in the tree.
For simplicity, your implementation does not need to support deletion of el-
ements from the tree. The methods you must implement are given in the BST
interface. You must implement a class called MyBST that implements this in-
terface. Make sure your class passes the tests in Test5.

NB: You must implement this class yourself and not use a built in library
or one you�ve found.

The BST.java interface and BSTNode.java classes are provided for you, you
must not change these in any way. The BST interface describes how each of
the functions you are required to implement are supposed to work. A test class
called Test5 is provided which can be used to test your binary search tree works
correctly, if you build your tree correctly when you run Test5 all tests are passed.

To complete this assignment you must:
1. Create a class called MyBST.java which implements the BST interface
2. Write all of the required methods given by the interface
3. Ensure that your list passes all of the tests in Test5

This assignment is worth 10% of your final grade, marks will be allocated as
follows:
� Creating MyBST class with all of the required fields and methods − 1
mark
� Correctly implementing top method − 1 mark
� Correctly implementing insert method − 2 marks
� Correctly implementing output method − 2 marks
� Correctly implementing find method − 2 marks
� Code structure and comments − 2 marks
If you are unclear about any of this information, please ask.


BST file


import java.util.ArrayList;

/**
* This is the interface you must implement to complete the assignment.
*
* It is an interface to a binary search tree for storing integers,
* supporting insertion and output. The BST must support insertion
* of duplicate elements (by maintaining a counter at each node).
*
* Obviously, a real implementation would normally also require a method
* for deleting elements from the tree. This is omitted here for
* simplicity.
*
* The last method wouldn't be present in an actual real-world
* implementation, but you must implement it so that we can test
* that your program builds binary search trees with the correct
* structure.
*
* @author Ian McDonald
*/
public interface BST {

/**
* Insert an integer into the BST.
*
* This must create a node if the number doesn't already exist and put
* it in correct place. If it does exist then it must add 1 to the count.
*
* @param n the integer to add
*/
void insert(int n);

/**
* This method must output the content of the BST into an ArrayList. The
* integers must be output in correct order (i.e. do not sort the ArrayList after
* adding the items). If the counter for a number
* in the BST is N, then this number must be output N times.
*
* @return an array list containing the list of integers
*/
ArrayList<Integer> output();

/**
* This method gets the top of the tree.
*
* @returnthe top of the tree or null if empty
*/
BSTNode top();

/**
*
* This recursive method searches the tree for a given value and returns true if the value is
* found and false if it is not found. The method must be defined recursively
* @param an int which isthe value to find
* @param BSTNode the root of the current tree
* @return true or false
*/
boolean find(int n, BSTNode r);
}






BSTNode file


/**
* This class contains the basic node structure for the binary search tree.
*/
public class BSTNode {

// Reference to left node
private BSTNode left;

// Reference to right node
private BSTNode right;

// The data stored at the node
private Integer data;

// The number of data items stored at the node
private Integer count;

/**
* The default constructor.
*
* Initializes count to one.
*/
public BSTNode() {
count = 1;
}

/**
* Constructor that takes data.
*
* Initializes count to one.
*
* @param data the data
* @param left a reference to the left node
*/
public BSTNode(Integer data, BSTNode left, BSTNode right) {
this();
this.data = data;
this.left = left;
this.right = right;
}

/**
* @return the count
*/
public Integer getCount() {
return count;
}

/**
* @param count the count to increment
*/
public void increment() {
this.count++;
}

/**
* @return the data
*/
public Integer getData() {
return data;
}

/**
* @param data the data to set
*/
public void setData(Integer data) {
this.data = data;
}

/**
* @return the left node
*/
public BSTNode getLeft() {
return left;
}

/**
* @param left the left node to set
*/
public void setLeft(BSTNode left) {
this.left = left;
}

/**
* @return the right node
*/
public BSTNode getRight() {
return right;
}

/**
* @param right the right node to set
*/
public void setRight(BSTNode right) {
this.right = right;
}
}





Test5 file


import java.util.*;

public class Test5 {

/**
* Checks whether given tree has BST property. Assumes that given
* root is not null.
*
* @param node the root of the subtree to check
* @param minAndMax two-element array that contains minimum and maximum
* value of subtree when method returns
* @return true if the subtree satisfies BST property and false otherwise
*/
public static boolean checkBSTProperty(BSTNode root, int[] minAndMax) {

// Array to hold minimum and maximum from left subtree
int[] minAndMaxLeft = new int[2];

// Checks based on left subtree
if (root.getLeft() != null) {
if (!checkBSTProperty(root.getLeft(), minAndMaxLeft)) {

// Property does not hold for left subtree
return false;

} else if (root.getData() <= minAndMaxLeft[1]) {

// Property does not hold for current node
// because current number is not greater than
// maximum from left subtree
return false;

}
}

// Array to hold minimum and maximum from righ subtree
int[] minAndMaxRight = new int[2];

// Checks based on right subtree
if (root.getRight() != null) {
if (!checkBSTProperty(root.getRight(), minAndMaxRight)) {

// Property does not hold for right subtree
return false;

} else if (root.getData() >= minAndMaxRight[0]) {

// Property does not hold for current node
// because current number is not smaller than
// minimum from right subtree
return false;
}
}

// Compute minimum and maximum for current subtree
// based on the fact that current subtree has BST property
if (root.getRight() != null) {
minAndMax[1] = minAndMaxRight[1];
} else {
minAndMax[1] = root.getData();
}
if (root.getLeft() != null) {
minAndMax[0] = minAndMaxLeft[0];
} else {
minAndMax[0] = root.getData();
}

// This subtree checks out
return true;
}

/**
* The main method with test case.
* @param args
*/
public static void main(String[] args) {

MyBST m = new MyBST();
if (m.top() == null)
System.out.println("PASS top() works on empty tree");
else
System.out.println("FAIL top() fails on empty tree");

m.insert(5);
m.insert(3);
m.insert(7);
m.insert(5);
m.insert(2);
m.insert(9);
m.insert(5);
m.insert(2);

BSTNode top = m.top();
if (top != null) {
System.out.println("PASS root node exists");
} else {
System.out.println("FAIL root node does not exist");
}
if (checkBSTProperty(top, new int[2])) {
System.out.println("PASS tree has BST property");
} else {
System.out.println("FAIL tree does not have BST property");
}
if(m.find(9, top))
System.out.println("PASS found value 9");
else
System.out.println("FAIL did not find value 9");
if(m.find(6, top))
System.out.println("FAIL returned true when searching for 6");
else
System.out.println("PASS did not find value 6");
ArrayList<Integer> il = m.output();
ArrayList<Integer> correctOutput = new ArrayList<Integer>();
Integer[] arr = {2, 2, 3, 5, 5, 5, 7, 9};
correctOutput.addAll(Arrays.asList(arr));
if (il.equals(correctOutput)) {
System.out.println("PASS output is correct");
} else {
System.out.println("FAIL output is not correct");
}
}
}


MyBST.java ( Here is my Code below)



Here is the output from eclipse:


PASS top() works on empty tree
PASS root node exists
PASS tree has BST property
PASS found value 9
FAIL returned true when searching for 6
PASS output is correct


[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]

[ May 15, 2008: Message edited by: hong Li ]
[ May 15, 2008: Message edited by: hong Li ]
hong Li
Greenhorn

Joined: May 15, 2008
Posts: 4
Sorry My first post, might be a little bit mess
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38392
    
  23
Welcome to the Ranch.

Please edit your post to add code tags round the other classes. Highlight the code, click the code button and voila!

You have made the error of using the MyBST to add data to a BST node. That is something the node itself should do.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11239
    
  16

I may have missed it, but I don't see an actual question. Remember, we are not here to do your work for you. people will bend over backwards to HELP you, but YOU have to do the work. Simply posting "here's my homework assignment" will annoy most people, who will then just ignore your post.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: BST problem (Online waiting)