Need help with one of my java classes : Import bridges.base.BSTElement to allow
ID: 3686235 • Letter: N
Question
Need help with one of my java classes :
Import bridges.base.BSTElement to allow you to use BSTElement objects
- Replace every instance and operation of the BinNode class with a BSTElement object and its equivalent methods
- Add methods to perform each type of traversal: preorder, postorder, inorder
- Add a method to count the number of leaf nodes and assign each a particular color or opacity
- Add a method to count the number of internal nodes and assign each a particular color or opacity
- Add a method to count the number of nodes with two children and assign each a particular color or opacity
- Add a method to determine the height of the tree (the longest path length)
Java Code :
import bridges.connect.Bridges;
import bridges.base.BSTElement;
/** Binary Search Tree implementation for Dictionary ADT */
class BST<Key extends Comparable<? super Key>, E> implements Dictionary<Key, E> {
private BSTNode<Key,E> root; // Root of the BST
private int nodecount; // Number of nodes in the BST
/** Constructor */
BST() { root = null; nodecount = 0; }
/** Reinitialize tree */
public void clear() { root = null; nodecount = 0; }
/** Insert a record into the tree.
@param k Key value of the record.
@param e The record to insert. */
public void insert(Key k, E e) {
root = inserthelp(root, k, e);
nodecount++;
}
/** @return The current subtree, modified to contain
the new item */
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt, Key k, E e) {
if (rt == null)
return new BSTNode<Key,E>(k, e);
if (rt.key().compareTo(k) > 0)
rt.setLeft(inserthelp(rt.left(), k, e));
else
rt.setRight(inserthelp(rt.right(), k, e));
return rt;
}
/** Remove a record from the tree.
@param k Key value of record to remove.
@return The record removed, null if there is none. */
public E remove(Key k) {
E temp = findhelp(root, k); // First find it
if (temp != null) {
root = removehelp(root, k); // Now remove it
nodecount--;
}
return temp;
}
/** Remove and return the root node from the dictionary.
@return The record removed, null if tree is empty. */
public E removeAny() {
if (root == null) return null;
E temp = root.element();
root = removehelp(root, root.key());
nodecount--;
return temp;
}
/** Remove a node with key value k
@return The tree with the node removed */
private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
rt.setLeft(removehelp(rt.left(), k));
else if (rt.key().compareTo(k) < 0)
rt.setRight(removehelp(rt.right(), k));
else { // Found it
if (rt.left() == null) return rt.right();
else if (rt.right() == null) return rt.left();
else { // Two children
BSTNode<Key,E> temp = getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
return rt;
}
private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(deletemin(rt.left()));
return rt;
}
private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt;
return getmin(rt.left());
}
/** @return Record with key value k, null if none exist.
@param k The key value to find. */
public E find(Key k) { return findhelp(root, k); }
private E findhelp(BSTNode<Key,E> rt, Key k) {
if (rt == null)
return null;
if (rt.key().compareTo(k) > 0)
return findhelp(rt.left(), k);
else if (rt.key().compareTo(k) == 0)
return rt.element();
else
return findhelp(rt.right(), k);
}
/** @return The number of records in the dictionary. */
public int size() { return nodecount; }
/** Inorder Traversal */
public void inorder() {
inorderHelp( root );
}
private void inorderHelp( BSTNode r ) {
return;
}
/** Postorder Traversal */
public void postorder() {
postorderHelp( root );
}
private void postorderHelp( BSTNode r ) {
return;
}
/** Preorder Traversal */
public void preorder() {
preorderHelp( root );
}
private void preorderHelp( BSTNode r ) {
return;
}
/** Count the number of leaf nodes */
public Integer countLeaves() {
return countLeafHelp( root );
}
private Integer countLeafHelp( BSTNode r ) {
return -1;
}
/** Count the number of internal nodes */
public Integer countInternalNodes() {
return countInternalNodes( root );
}
private Integer countInternalNodes( BSTNode r ) {
return -1;
}
/** Count the nodes with two children */
public Integer countTwoChildNodes() {
return twoChildHelp( root );
}
private Integer twoChildHelp( BSTNode r ) {
return -1;
}
/** Compute the max path length */
public Integer getMaxPathLength() {
return maxPathHelp( root );
}
private Integer maxPathHelp( BSTNode r ) {
return -1;
}
}
Explanation / Answer
Note:
In the given code, the required code is added and solution is prepared.
Given code:
//BST.java
import bridges.connect.Bridges;
import bridges.base.BSTElement;
/** Binary Search Tree implementation for Dictionary ADT */
class BST<Key extends Comparable<? super Key>, E> implements Dictionary<Key, E>
{
private BSTNode<Key,E> root; // Root of the BST
private int nodecount; // Number of nodes in the BST
/** Constructor */
BST() { root = null; nodecount = 0; }
/** Reinitialize tree */
public void clear() { root = null; nodecount = 0; }
/** Insert a record into the tree.
@param k Key value of the record.
@param e The record to insert. */
public void insert(Key k, E e) {
root = inserthelp(root, k, e);
nodecount++;
}
/** @return The current subtree, modified to contain
the new item */
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt, Key k, E e) {
if (rt == null)
return new BSTNode<Key,E>(k, e);
if (rt.key().compareTo(k) > 0)
rt.setLeft(inserthelp(rt.left(), k, e));
else
rt.setRight(inserthelp(rt.right(), k, e));
return rt;
}
/** Remove a record from the tree.
@param k Key value of record to remove.
@return The record removed, null if there is none. */
public E remove(Key k) {
E temp = findhelp(root, k); // First find it
if (temp != null) {
root = removehelp(root, k); // Now remove it
nodecount--;
}
return temp;
}
/** Remove and return the root node from the dictionary.
@return The record removed, null if tree is empty. */
public E removeAny() {
if (root == null) return null;
E temp = root.element();
root = removehelp(root, root.key());
nodecount--;
return temp;
}
/** Remove a node with key value k
@return The tree with the node removed */
private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
rt.setLeft(removehelp(rt.left(), k));
else if (rt.key().compareTo(k) < 0)
rt.setRight(removehelp(rt.right(), k));
else { // Found it
if (rt.left() == null) return rt.right();
else if (rt.right() == null) return rt.left();
else { // Two children
BSTNode<Key,E> temp = getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
return rt;
}
private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(deletemin(rt.left()));
return rt;
}
private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt;
return getmin(rt.left());
}
/** @return Record with key value k, null if none exist.
@param k The key value to find. */
public E find(Key k) { return findhelp(root, k); }
private E findhelp(BSTNode<Key,E> rt, Key k) {
if (rt == null)
return null;
if (rt.key().compareTo(k) > 0)
return findhelp(rt.left(), k);
else if (rt.key().compareTo(k) == 0)
return rt.element();
else
return findhelp(rt.right(), k);
}
/** @return The number of records in the dictionary. */
public int size() { return nodecount; }
/** Inorder Traversal */
public void inorder() {
inorderHelp( root );
}
private void inorderHelp( BSTNode r ) {
return;
}
/** Postorder Traversal */
public void postorder() {
postorderHelp( root );
}
private void postorderHelp( BSTNode r ) {
return;
}
/** Preorder Traversal */
public void preorder() {
preorderHelp( root );
}
private void preorderHelp( BSTNode r ) {
return;
}
/** Count the number of leaf nodes */
public Integer countLeaves() {
return countLeafHelp( root );
}
private Integer countLeafHelp( BSTNode r ) {
return -1;
}
/** Count the number of internal nodes */
public Integer countInternalNodes() {
return countInternalNodes( root );
}
private Integer countInternalNodes( BSTNode r ) {
return -1;
}
/** Count the nodes with two children */
public Integer countTwoChildNodes() {
return twoChildHelp( root );
}
private Integer twoChildHelp( BSTNode r ) {
return -1;
}
/** Compute the max path length */
public Integer getMaxPathLength() {
return maxPathHelp( root );
}
private Integer maxPathHelp( BSTNode r ) {
return -1;
}
}
Required code:
/*--------------------------------*/
//BSTNode.java
class BSTNode<Key, E> implements BinNode<E>
{
// declare the required variables
private Key bst_key;
private E bst_element;
private BSTNode<Key,E> bst_left;
private BSTNode<Key,E> bst_right;
// No argument constructor
public BSTNode()
{
bst_left = bst_right = null;
}
// Constructor with arguments
public BSTNode(Key bk, E bval)
{
bst_left = bst_right = null;
bst_key = bk;
bst_element = bval;
}
// Constructor with arguments
public BSTNode(Key bk, E bval,BSTNode<Key,E> lt, BSTNode<Key,E> rt)
{
bst_left = lt;
bst_right = rt;
bst_key = bk;
bst_element = bval;
}
// method to get the key value
public Key bst_key()
{
return bst_key;
}
// method to set the key value
public void setKey(Key bk)
{
bst_key = bk;
}
// method to get the element value
public E bst_element()
{
return bst_element;
}
// method to set the element value
public void setElement(E bv) { bst_element = bv; }
// method to get the left child
public BSTNode<Key,E> bst_left()
{
return bst_left;
}
// method to set the left child
public void setLeft(BSTNode<Key,E> bp)
{
bst_left = bp;
}
// method to get the right child
public BSTNode<Key,E> bst_right()
{
return bst_right;
}
// method to set set the right child
public void setRight(BSTNode<Key,E> bp)
{
bst_right = bp;
}
// method to check a leaf node
public boolean isLeaf()
{
return (bst_left == null) && (bst_right == null);
}
}
/*--------------------------------*/
//BSTTest.java
import java.io.*;
public class BSTTest extends junit.framework.TestCase
{
private Dictionary<Integer, Integer> Dic1;
public void setUp()
{
Dic1 = new BST<Integer, Integer>();
}
// method1 to insert the values in BST
public void testBST1()
{
assertEquals(Dic1.size(), 0);
Dic1.insert(45, 45);
assertEquals(Dic1.size(), 1);
Dic1.remove(25);
assertEquals(Dic1.size(), 1);
Dic1.remove(45);
assertEquals(Dic1.size(), 0);
Dic1.clear();
assertEquals(Dic1.size(), 0);
Dic1.insert(35, 35);
Dic1.insert(19, 19);
Dic1.insert(25, 25);
assertEquals(Dic1.size(), 3);
Dic1.clear();
assertEquals(Dic1.size(), 0);
}
// method2 to insert the values in BST
public void testBST2()
{
Dic1.insert(75, 75);
assertEquals(Dic1.toString(), "75 ");
Dic1.insert(36, 36);
Dic1.insert(21, 21);
Dic1.insert(18, 18);
Dic1.insert(16, 16);
assertEquals(Dic1.toString(), "25 27 30 45 80 ");
Dic1.insert(19, 19);
Dic1.insert(99, 99);
Dic1.insert(91, 91);
Dic1.insert(96, 96);
assertEquals(Dic1.toString(), "25 27 29 21 36 71 91 96 99 ");
Dic1.insert(1, 1);
assertEquals(Dic1.size(), 11);
Dic1.insert(1, 1);
assertEquals(Dic1.toString(), "2 2 16 18 19 21 36 71 91 96 99 ");
assertEquals(Dic1.size(), 12);
assertEquals(Dic1.find(99), null);
assertEquals(Dic1.find(101), new Integer(101));
assertEquals(Dic1.find(16), new Integer(16));
assertEquals(Dic1.find(71), new Integer(71));
assertEquals(Dic1.remove(16), new Integer(16));
assertEquals(Dic1.size(), 11);
assertEquals(Dic1.remove(34), null);
assertEquals(Dic1.size(), 11);
assertEquals(Dic1.remove(71), new Integer(71));
assertEquals(Dic1.size(), 8);
Dic1.clear();
assertEquals(Dic1.size(), 0);
}
}
/*--------------------------------*/
//BinNode.java
public interface BinNode<E>
{
// to get and set the value of element
public E element();
public void setElement(E bv);
// returns the left child
public BinNode<E> left();
// returns The right child
public BinNode<E> right();
//to check leaf node
public boolean isLeaf();
}
/*--------------------------------*/
//Dictionary.java
public interface Dictionary<Key, E>
{
// to initialize the dictionary
public void clear();
// to insert the record
public void insert(Key k, E e);
// to remove the record
public E remove(Key k);
// to remove arbitrary record
public E removeAny();
// to find a matching record
public E find(Key k);
// to return number of record
public int size();
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.