We have discussed binary search trees, where the nodes in a tree are stored such that an inorder traversal of the tree will produce a list of the data in ascending order. In this lab, you must create a descending order version of the BST, where the largest value is stored as the leftmost node, and the smallest value is stored as the rightmost node. Complete the binary search tree class, named BST and stored in the file named BST.java. The following methods are required for your code to work with the grading tests. a constructor to create an empty tree (This is provided in the template.) public void insert(int key) : the key should be inserted (in a new Node) in the tree, such that the tree is in descending order. public void delete(int key) : the given key should be removed from the tree. public String inorderTraversal() : Perform an inorder traversal of the tree, constructing a String that contains the items in the tree, in the order visited, with a space between each item. Note 1: This week, the grading tests will call the BST methods, and examine the Strings returned by the traversal method. The traversal method should be very similar to the one you wrote last week. The format of the Strings must match the expected format. Note 2: You do not need to write a main method (it is built into the grading tests). BST.Java class BST{ private class Node { public int item; public Node left; public Node right; public Node (int i) { //makes a leaf item = i; left = right = null; } //***insert Node methods here*** }//end class Node private Node root; public BST(){ root = null; } public String inorderTraversal() { }//end inorderTraversal public void insert( int key ){ }//end insert public void delete( int key ){ }//end delete //***insert tree methods here*** }//end class BST Test feedback Inserting 42, 5, 18, 72 produces incorrect output. The output should be " 72 42 18 5" In JAVA Programming
We have discussed binary search trees, where the nodes in a tree are stored such that an inorder traversal of the tree will produce a list of the data in ascending order. In this lab, you must create a descending order version of the BST, where the largest value is stored as the leftmost node, and the smallest value is stored as the rightmost node.
Complete the binary search tree class, named BST and stored in the file named BST.java. The following methods are required for your code to work with the grading tests.
- a constructor to create an empty tree (This is provided in the template.)
- public void insert(int key) : the key should be inserted (in a new Node) in the tree, such that the tree is in descending order.
- public void delete(int key) : the given key should be removed from the tree.
- public String inorderTraversal() : Perform an inorder traversal of the tree, constructing a String that contains the items in the tree, in the order visited, with a space between each item.
Note 1: This week, the grading tests will call the BST methods, and examine the Strings returned by the traversal method. The traversal method should be very similar to the one you wrote last week. The format of the Strings must match the expected format.
Note 2: You do not need to write a main method (it is built into the grading tests).
BST.Java
class BST{
private class Node {
public int item;
public Node left;
public Node right;
public Node (int i) { //makes a leaf
item = i;
left = right = null;
}
//***insert Node methods here***
}//end class Node
private Node root;
public BST(){
root = null;
}
public String inorderTraversal() {
}//end inorderTraversal
public void insert( int key ){
}//end insert
public void delete( int key ){
}//end delete
//***insert tree methods here***
}//end class BST
Test feedback
Inserting 42, 5, 18, 72 produces incorrect output. The output should be " 72 42 18 5"
In JAVA Programming
Step by step
Solved in 2 steps with 1 images
