implement the following methods for the Binary Search Tree where indicated in th
ID: 3732262 • Letter: I
Question
implement the following methods for the Binary Search Tree where indicated in the java code:
import java.util.Scanner;
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // root of binary search tree
private class Node {
private Key key; // sorted by key
private Value value; // data stored in the node
private Node left, right; // pointers to left and right subtrees
private int size; // number of nodes in subtree
public Node(Key k, Value v) {
this.key = k;
this.value = v;
}
}
// Insert key-value pairs in BST, if a key already exists update the value
public void insert(Key key, Value value){
if (root == null)
root = node;
left = null;
right = null;
else
cur = root;
while(cur != null)
{
if(node.compareTo(cur)
if(left = null)
left = node;
cur = null;
else
cur = left;
else
if(right = null)
right = node;
cur = null;
else
cur = right;
left = null;
right = null;return root;
// Implement insertion of a key-value pair in a BST.
}
// Search BST for a given key
public Value get(Key key) {
// Implement search for a given key
return null;
}
public void inorder(Node root){
// Implement Inorder Traversal
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
BST<Integer, String> bst = new BST<Integer, String>();
while(input.hasNext()){
int key = input.nextInt();
if(key == -1) break;
String value = input.next();
bst.insert(key, value);
}
System.out.println("Search for key: 20");
System.out.println(bst.get(20));
System.out.println("Inorder Traversal prints:");
bst.inorder(bst.root);
}
}
Explanation / Answer
import java.util.Scanner;
public class BST<Key extends Comparable<Key>, Value> {
private Node root; // root of binary search tree
private class Node {
private Key key; // sorted by key
private Value value; // data stored in the node
private Node left, right; // pointers to left and right subtrees
private int size; // number of nodes in subtree
public Node(Key k, Value v) {
this.key = k;
this.value = v;
}
}
// Insert key-value pairs in BST, if a key already exists update the value
public void insert(Key key, Value value){
if (root == null){
root.left = null;
root.right = null;
}else
cur = root;
while(cur != null)
{
if(node.compareTo(cur)
if(left = null)
left = node;
cur = null;
else
cur = left;
else
if(right = null)
right = node;
cur = null;
else
cur = right;
left = null;
right = null;return root;
// Implement insertion of a key-value pair in a BST.
}
// Search BST for a given key
public Value Search(Node root, Key key) {
// Implement Inorder Traversal
if (root != null){
inorder(root.left);
if(root.key.compareTo(key)==0)
return root.value;
inorder(root.right);
}
return null;
}
public Value get(Key key) {
// Implement search for a given key
return Search(root, key);
}
public void inorder(Node root){
// Implement Inorder Traversal
if(root==null)
return ;
inorder(root.left);
System.out.println(root.value);
inorder(root.right);
}
public static void main(String[] args){
Scanner input = new Scanner(System.in);
BST<Integer, String> bst = new BST<Integer, String>();
while(input.hasNext()){
int key = input.nextInt();
if(key == -1) break;
String value = input.next();
bst.insert(key, value);
}
System.out.println("Search for key: 20");
System.out.println(bst.get(20));
System.out.println("Inorder Traversal prints:");
bst.inorder(bst.root);
}
}
============
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.