Need to solve this import java.util.Random; public class BST<Key extends Compara
ID: 3715708 • Letter: N
Question
Need to solve this
import java.util.Random;
public class BST<Key extends Comparable, Value> {
private Node root;
// note: the outer class has direct access to values in this inner class
private class Node {
private Key key;
private Value value;
private Node lChild;
private Node rChild;
// number of nodes at this subtree
// N for the root == # of nodes in entire tree
// N for lead node == 1
private int N;
public Node(Key key, Value value, int N) {
// TODO
this.key = key;
this.value=value;
this.N=N;
}
}
//return number of nodes in subtree
public int size(Node n)
{
int lSize = 0;
int rSize = 0;
n = root;
if(n == null)
{
return 0;
}
else
{
if(n.lChild != null)
{
lSize = n.lChild.N;
}
if(n.rChild != null)
{
rSize = n.rChild.N;
}
//root size + left child size + right child size
return 1 + lSize + rSize;
}
}
public int size() {
return size(root); // TODO: return # of nodes in the tree
}
// TODO: return value associated with key, or null if key doesn't exist
public Value get(Key key)
{
Node n = root;
while(n != null)
{
int comp = key.compareTo(n.key);
if(comp < 0)
{
n = n.lChild;
if(n.key != key)
{
return null;
}
else
{
return n.value;
}
}
else if (comp > 0)
{
n = n.rChild;
if(n.key != key)
{
return null;
}
else
{
return n.value;
}
}
else //comp == 0
{
return n.value;
}
}
//return null if key is not in the tree
return null;
}
public Node put(Node n, Value val, Key key)
// inserts the key value pair into the tree
// performs an in order walk of the tree printing the values
{
//key not in tree -> add new node
if(n == null)
{
return new Node(key, val, 1);
}
//key found in tree -> reset value
int comp = key.compareTo(n.key);
if(comp < 0)
{
n.lChild = put(n.lChild, val, key);
}
else if(comp > 0)
{
n.rChild = put(n.rChild, val, key);
}
else //comp == 0
{
n.value = val;
}
//root size + left child size + right child size
//n.N = 1 + size(n.lChild) + size(n.rChild);
return n;
}
public void put(Key key, Value val) {
root = put(root, val, key); // TODO: insert key/value pair into tree
}
public void preOrder()
{
preOrder(root);
}
//pre-order: root, left, right
public void preOrder(Node n)
{
if(n == null)
{
return;
}
else
{
System.out.print(n.key + " ");
preOrder(n.lChild);
preOrder(n.rChild);
}
}
public void postOrder()
{
postOrder(root);
}
//post-order: left, right, root
public void postOrder(Node n)
{
if(n == null)
{
return;
}
else
{
preOrder(n.lChild);
preOrder(n.rChild);
System.out.print(n.key + " ");
}
}
public void inOrder()
{
inOrder(root);
}
//in-roder: left, root, right
public void inOrder(Node n)
{
if(n == null)
{
return;
}
else
{
preOrder(n.lChild);
System.out.print(n.key + " ");
preOrder(n.rChild);
}
}
public void walk() {
// TODO: walk the tree in order & print the values
}
// Returns a pre-order, post-order,
//and in-order walk of the tree printing the values
public void toString(BST another)
{
}
public boolean isEqual(BST another)
// returns true is this tree (using root node) is exactly
//same as another BST, return false otherwise.
{
boolean isEqual = true;
if(this.root == null && another == null)
{
isEqual = true;
}
else if(this.root.value == another.root.value )
{
isEqual = true;
}
else
{
isEqual = false;
}
return isEqual;
}
public static void main(String[] args) {
Random rand = new Random();
BST<Integer, Character> tree = new BST<>();
for (int i = 0; i < 25; i++) {
int key = rand.nextInt(26) + 'a';
char val = (char) key;
tree.put(key, val);
}
// note: not all of these chars will end up being generated from the for loop
// some of these return values will be null
System.out.println(tree.get((int) 'a'));
System.out.println(tree.get((int) 'b'));
System.out.println(tree.get((int) 'c'));
System.out.println(tree.get((int) 'f'));
System.out.println(tree.get((int) 'k'));
System.out.println(tree.get((int) 'x'));
tree.walk();
// TODO: test equals and toString methods
}
}
deve opmen Wewii thenbe nooing epprepriete iunit ests to tettse pregrem nage's ice, to trve ryn gf th, rast ?.ier men th, reon key, arg than the rost's wger * This propeny rcies for esch coein he drection te * e: Trees "re ?¡rast-wmys impereercee w" rearion becnue t i very nstr.ta dbExplanation / Answer
import java.util.Random;
public class BST<Key extends Comparable, Value> {
private Node root;
// note: the outer class has direct access to values in this inner class
private class Node {
private Key key;
private Value value;
private Node lChild;
private Node rChild;
// number of nodes at this subtree
// N for the root == # of nodes in entire tree
// N for lead node == 1
private int N;
public Node(Key key, Value value, int N) {
// TODO
this.key = key;
this.value=value;
this.N=N;
}
}
public BST() {
root = null;
}
public Node getRoot() {
return root;
}
public boolean isEmpty() {
return null == root;
}
//return number of nodes in subtree
public int size(Node n)
{
int lSize = 0;
int rSize = 0;
n = root;
if(n == null)
{
return 0;
}
else
{
if(n.lChild != null)
{
lSize = n.lChild.N;
}
if(n.rChild != null)
{
rSize = n.rChild.N;
}
//root size + left child size + right child size
return 1 + lSize + rSize;
}
}
public int size() {
return size(root); // TODO: return # of nodes in the tree
}
// TODO: return value associated with key, or null if key doesn't exist
public Value get(Key key)
{
Node n = root;
while(n != null)
{
int comp = key.compareTo(n.key);
if(comp < 0)
{
n = n.lChild;
if(n.key == key)
{
return n.value;
}
}
else if (comp > 0)
{
n = n.rChild;
if(n.key == key)
{
return n.value;
}
}
else //comp == 0
{
return n.value;
}
}
//return null if key is not in the tree
return null;
}
public Node put(Node n, Value val, Key key)
// inserts the key value pair into the tree
// performs an in order walk of the tree printing the values
{
//key not in tree -> add new node
if(n == null)
{
return new Node(key, val, 1);
}
//key found in tree -> reset value
int comp = key.compareTo(n.key);
if(comp < 0)
{
n.lChild = put(n.lChild, val, key);
}
else if(comp > 0)
{
n.rChild = put(n.rChild, val, key);
}
else //comp == 0
{
n.value = val;
}
//root size + left child size + right child size
//n.N = 1 + size(n.lChild) + size(n.rChild);
return n;
}
public void put(Key key, Value val) {
root = put(root, val, key); // TODO: insert key/value pair into tree
}
public void preOrder()
{
preOrder(root);
}
//pre-order: root, left, right
public void preOrder(Node n)
{
if(n == null)
{
return;
}
else
{
System.out.print(n.key + " ");
preOrder(n.lChild);
preOrder(n.rChild);
}
}
public void postOrder()
{
postOrder(root);
}
//post-order: left, right, root
public void postOrder(Node n)
{
if(n == null)
{
return;
}
else
{
preOrder(n.lChild);
preOrder(n.rChild);
System.out.print(n.key + " ");
}
}
public void inOrder()
{
inOrder(root);
}
//in-roder: left, root, right
public void inOrder(Node n)
{
if(n == null)
{
return;
}
else
{
preOrder(n.lChild);
System.out.print(n.key + " ");
preOrder(n.rChild);
}
}
public void walk() {
// TODO: walk the tree in order & print the values
}
// Returns a pre-order, post-order,
//and in-order walk of the tree printing the values
public void toString(BST another)
{
}
public boolean isEqual(BST another)
// returns true is this tree (using root node) is exactly
//same as another BST, return false otherwise.
{
boolean isEqual = true;
if(this.root == null && another == null)
{
isEqual = true;
}
else if(this.root.value == another.root.value )
{
isEqual = true;
}
else
{
isEqual = false;
}
return isEqual;
}
public static void main(String[] args) {
Random rand = new Random();
BST<Integer, Character> tree = new BST<>();
for (int i = 0; i < 25; i++) {
int key = rand.nextInt(26) + 'a';
char val = (char) key;
// System.out.println("key "+key+" value "+val);
tree.put(key,val);
}
// note: not all of these chars will end up being generated from the for loop
// some of these return values will be null
System.out.println("my value: size"+(int)'a'+"size "+tree.size());
// you are using random method, SO the output we cannt expect exactly because
// Some times it gives NullPointerException.
System.out.println(tree.get((int) 'a'));
System.out.println(tree.get((int) 'b'));
System.out.println(tree.get((int) 'c'));
System.out.println(tree.get((int) 'f'));
System.out.println(tree.get((int) 'k'));
System.out.println(tree.get((int) 'x'));
tree.walk();
// TODO: test equals and toString methods
}
}
/* output:-
a
b
c
f
k
x
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.