Using the SortedInterface below, Write a Java class named BinaryTreeSortedList t
ID: 3578284 • Letter: U
Question
Using the SortedInterface below,
Write a Java class named BinaryTreeSortedList to implement the SortedList interface, using a linked Binary Search Tree.
public interface SortedListInterface<T extends Comparable<? super T>> {
/**
* Adds a new entry to this list in its proper order, if it does not match
* an existing object in the list.
*
* @param newEntry
* An object to be added to the list.
* @return True if the object was added to the list, otherwise return false.
*/
public boolean add(T newEntry);
/**
* Removes the only occurrence of a specified entry from this
* sorted list.
*
* @param anEntry
* The object to be removed.
* @return True if anEntry was located and removed; otherwise returns false.
*/
public boolean remove(T anEntry);
/**
* Sees whether this list contains a given entry.
*
* @param anEntry
* The object that is the desired entry.
* @return True if the list contains anEntry, or false if not.
*/
public boolean contains(T anEntry);
/** Removes all entries from this list. */
public void clear();
/**
* Gets the length of this list.
*
* @return the integer number of entries currently in the list.
*/
public int getLength();
/**
* Sees whether this list is empty.
*
* @return true if the list is empty, or false if not.
*/
public boolean isEmpty();
/**
* Retrieves all entries that are in this list in the order in which they
* occur in the list.
*
* @return A newly allocated array of all the entries in the list. Note: If
* the list is empty, the returned array is empty.
*/
// Note: Can change return type to Object[] if T[] causes problems
public T[] toArray();
/**
*
* @return the sorted list of values with a space between each value
*/
public String toString();
} // end SortedListInterface
Explanation / Answer
import java.util.Scanner;
/* Class Node */
class Node
{
NodePoint left_Node, right_Node;
int data;
/* Constructor */
public Node(int n)
{
left_Node = null;
right_Node = null;
data = n;
}
}
class BST
{
private NodePoint root;
/* Constructor */
public BST()
{
root = null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private Node insert(NodePoint node, int data)
{
if (node == null)
node = new NodePoint(data);
else
{
if (data <= node.data)
node.left_Node = insert(node.left_Node, data);
else
node.right_Node = insert(node.right_Node, data);
}
return node;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(NodePoint r)
{
if (r != null)
{
inorder(r.left);
System.out.print(r.data +" ");
inorder(r.right);
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(NodePoint r)
{
if (r != null)
{
System.out.print(r.data +" ");
preorder(r.left_Node);
preorder(r.right_Node);
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(NodePoint r)
{
if (r != null)
{
postorder(r.left_Node);
postorder(r.right_Node);
System.out.print(r.data +" ");
}
}
}
/* Class LinkedListBST */
public class BinaryTreeSortedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Linked List Binary Search Tree Test ");
char ch;
/* Accept input */
do
{
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
/* Display tree */
System.out.print(" Post order : ");
bst.postorder();
System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" In order : ");
bst.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.