Here are the class definitions of Node and List that implement a linked list cla
ID: 639044 • Letter: H
Question
Here are the class definitions of Node and List that implement a linked list class Node private Node next; private int key; Node (Node nxt, int keyValue); // constructor Node getNext); int getKey); void putNext (Node nxt); Class List // assume the class does not use a dummy Node private Node head; List) boolean exists(int ky);// returns true if v is in the list void insertAtHead(int ky); // inserts at the beginning of the list void insertAtTail(int ky); // inserts at the end of the list int removeFromHead void delete(int ky); // delete the element or do nothing if v doesn't exist int removeSmallest); // removes the Node containing the smallest key // constructor // Returns -1 if the list is emptjy // and returns that key. Returns -1 if the list is empty. // Could be duplicate entries, so remove the first int removeLargestO; // removes the Node containing the largest key // and returns that key. Returns -1 if the list is empty. // Could be duplicate entries, so remove the first int maxElement O; int sumO; int length); // calls the private version, doesn't delete the Node // calls the private version // calls the private version private int maxElement (Node x); private int sum(Node x); private int length (Node x); 1. Write the function void insertAtTail(int v). Don't add any class variables to the List class 2. Write the private function void delete(int ky, Node x) using only one reference variable that marches along the list (my notes use two reference variables, ref and prev) 3. Write the private recursive function int maxElement (Node x) 4. Write the private recursive function int sum (Node x) to find the sum of the keys stored in a List 5. Write the private recursive function int length(Node x) to find the number of keys in a List 6. Assume the addition of the two functions: public void recursiveDelete(int ky) I // calls the private version private Node recursiveDelete(int ky, Node n); Write both functions 7. On eLearning is a Java Program that implements a Binary Search Tree Add a public function int height () and its private recursive counterpart int height (BinaryNode) that returns the height of the tree. If the subtree is empty, return -1 8. Add a public function int countNodes() and its private recursive counterpart int countNodes (BinaryNode) that returns the number of nodes in the subtree. If the tree is empty, return 0 9. Add a public function void pruneLeaves () and its private recursive counterpart void pruneLeaves (BinaryNode) that deletes all nodes in the subtree that have no children, including the root if it is the only nodeExplanation / Answer
import java.util.Scanner;
/* Class Node */
class Node
{
Node left, right;
int data;
/* Constructor */
public Node(int n)
{
left = null;
right = null;
data = n;
}
}
/* Class BST */
class BST
{
private Node 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(Node node, int data)
{
if (node == null)
node = new Node(data);
else
{
if (data <= node.data)
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(Node 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(Node r)
{
if (r != null)
{
System.out.print(r.data +" ");
preorder(r.left);
preorder(r.right);
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(Node r)
{
if (r != null)
{
postorder(r.left);
postorder(r.right);
System.out.print(r.data +" ");
}
}
}
/* Class LinkedListBST */
public class LinkedListBST
{
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.