Answer To: CS 304 Homework Assignment 5 Due: 11:59pm, Thursday, April 1st This assignment is scored out of 75....
Kshitij answered on Apr 08 2021
SongBST/BST.java
SongBST/BST.java
/* Created by IntelliJ IDEA.
* Author: Kshitij Varshney (kshitijvarshne1)
* Date: 08-Apr-21
* Time: 4:50 PM
* File: BST.java
*/
package April.api09_21.SongBST;
import java.util.Stack;
public class BST {// instance variables
private BSTNode m_root;
private int m_size;
// constructor
public BST() {
m_root = null;
m_size = 0;
}
// This method returns the number of elements in the tree.
// Do not make any changes to this method!
public int size() {
return m_size;
}
// This method clears the content of the tree.
// Do not make any changes to this method!
public void clear() {
m_root = null;
m_size = 0;
}
// This non-recursive method takes a string and inserts it into the binary
// search tree, keeping the tree ordered.
public void add(String value) {
this.m_root = add(m_root, value);
}
private BSTNode add(BSTNode root, String value) {
if (root == null) {
root = new BSTNode(value);
m_size += 1;
return root;
} else if (root.getInfo().compareTo(value) < 0) {
root.setRight(add(root.getRight(), value));
} else if(root.getInfo().compareTo(value) > 0) {
root.setLeft(add(root.getLeft(), value));
}
return root;
}
// This non-recursive method returns a string that represents the in-order traversal
// of the binary search tree.
public String inOrder() {
// create an empty stack
String s = "";
Stack stack = new Stack();
// start from the root node (set current node to the root node)
BSTNode curr = this.m_root;
// if the current node is null and the stack is also empty, we are done
while (!stack.empty() || curr != null) {
// if the current node exists, push it into the stack (defer it)
// and move to its left child
if (curr != null) {
stack.push(curr);
curr = curr.getLeft();
} else {
// otherwise, if the current node is null, pop an element from
// the stack, print it, and finally set the current node to its
// right child
curr = stack.pop();
s = s + curr.getInfo() + " ";
curr = curr.getRight();
}
}
return s;
}
// This method returns the largest element in the binary search tree. You
// are not allowed to create any additional structures, including but not
// limited to arrays, stacks, queues, or other trees.
public String max() {
return max(this.m_root); // replace this statement with your own return
}
private String max(BSTNode m_root) {
BSTNode current = m_root;
while (current.getRight() != null)
current = current.getRight();
return (current.getInfo());
}
public int evaluate(BSTNode node) {
if (node == null) {
return 0;
}
if (isLeaf(node)) {
return Integer.valueOf(node.getInfo());
}
int x = evaluate(node.getLeft());
int y = evaluate(node.getRight());
return process(node.getInfo(), x, y);
}
public int process(String op, int x, int y)
{
if (op.equals("+")) { return x + y; }
if (op.equals("-")) { return x - y; }
if (op.equals("*")) { return x * y; }
if (op.equals("/")) { return x / y; }
return 0;
}
public static boolean isLeaf(BSTNode node) {
return node.getLeft() == null && node.getRight() == null;
}
}
SongBST/BSTNode.java
SongBST/BSTNode.java
/* Created by IntelliJ IDEA.
* Author: Kshitij Varshney (kshitijvarshne1)
* Date: 08-Apr-21
* Time: 4:51 PM
* File: BSTNode.java
*/
package April.api09_21.SongBST;
public class BSTNode {// data members
private String m_value;
private BSTNode m_left;
private BSTNode m_right;
// constuctor
public BSTNode(String value)
{
m_value = value;
m_left = null;
m_right = null;
}
// member methods
public String getInfo()
{
return m_value;
}
public BSTNode getLeft()
{
return m_left;
}
public BSTNode getRight()
{
return m_right;
}
public void setLeft(BSTNode left)
{
m_left = left;
}
public void setRight(BSTNode right)
{
m_right = right;
}
}
SongBST/Song.java
SongBST/Song.java
/* Created by IntelliJ IDEA.
* Author: Kshitij Varshney (kshitijvarshne1)
* Date: 08-Apr-21
* Time: 4:54 PM
* File: Song.java
*/
package April.api09_21.SongBST;
public class Song {// instance variables
private String m_artist;
private String m_title;
private Song m_link;
// constructor
public Song(String artist, String title)
{
m_artist = artist;
m_title = title;
m_link = null;
}
// getters and setters
public void setArtist(String artist)
{
m_artist = artist;
}
public String getArtist()
{
return m_artist;
}
public void setTitle(String title)
{
m_title = title;
}
public String getTitle()
{
return m_title;
}
public void setLink(Song link)
{
m_link = link;
}
public Song getLink()
{
return m_link;
}
}
SongBST/SongList.java
SongBST/SongList.java
/* Created by IntelliJ IDEA.
* Author: Kshitij Varshney (kshitijvarshne1)
* Date: 08-Apr-21
* Time: 4:53 PM
* File: SongList.java
*/
package April.api09_21.SongBST;
public class SongList {// instance variables
private Song head;
private int m_numElements;
// constructor
// Do not make any changes to this method!
public SongList() {
head = null;
m_numElements = 0;
}
// check whether the list is empty
// Do not make any changes to this method!
boolean isEmpty() {
return head == null;
}
// return the size of the list (# of Song nodes)
// Do not make any changes to this method!
public int size() {
return m_numElements;
}
// add a new Song to the circular linked list with the given artist and
// title, keeping the list sorted by *song title*.
public void add(String artist, String title) {
m_numElements += 1;
Song newSong = new Song(artist, title);
if(isEmpty()){
head =newSong;
newSong.setLink(head);
}
else
if(title.toLowerCase().compareTo(head.getTitle().toLowerCase())<0 &&
head.getLink()==head){
Song t= head;
head= newSong;
newSong.setLink(t);
t.setLink(head);
}
else
if(title.toLowerCase().compareTo(head.getTitle().toLowerCase())>=0 &&
head.getLink()==head){
head.setLink(newSong);
newSong.setLink(head);
}
else{
Song temp = head;
Song lasAdd=head;
while(temp.getLink()!= head &&
title.toLowerCase().compareTo(temp.getTitle().toLowerCase())>=0){
lasAdd=temp;
temp=temp.getLink();
}
if(temp.getLink()==head){
temp.setLink(newSong);
newSong.setLink(head);
}
else{
newSong.setLink(lasAdd.getLink());
lasAdd.setLink(newSong);
}
}
}
// remove a Song associated with the given artist and title from the
// keeping the list sorted by *song title*.
public boolean remove(String artist, String title) {
if(!isEmpty()){
if(head.getTitle().equalsIgnoreCase(title) &&
head.getArtist().equalsIgnoreCase(artist)){
Song t= head;
head=head.getLink();
Song one = head;
while(one.getLink()!=t){
one =one.getLink();
}
one.setLink(head);
m_numElements-=1;
return true;
}
else{
Song t=head;
t=t.getLink();
if(t.getTitle().equalsIgnoreCase(title) &&
t.getArtist().equalsIgnoreCase(artist)){
t=t.getLink().getLink();
return true;
}
Song temp1 = head;
Song lasAdd=head;
while(temp1.getLink()!= head){
lasAdd=temp1;
temp1=temp1.getLink();
}
if(lasAdd.getLink().getArtist().equalsIgnoreCase(artist) &&
lasAdd.getLink().getTitle().equalsIgnoreCase(title)){
lasAdd=head;
m_numElements-=1;
return true;
}
Song temp = head;
while(temp.getLink().getLink()!=head){
if(temp.getLink().getArtist().equalsIgnoreCase(artist) &&
temp.getLink().getLink()==head){
temp.setLink(head);
m_numElements-=1;
return true;
}
else if(temp.getArtist().equalsIgnoreCase(artist) &&
temp.getLink()!=head) {
temp.setLink(temp.getLink().getLink());
m_numElements-=1;
return true;
}
temp=temp.getLink();
}
}
}
return false;
}
// build and return a circular linked list that contains all songs from
// given artist
public SongList buildList(String artist) {
SongList newList= new SongList();
Song temp = head;
while(temp.getLink()!=head){
if(temp.getArtist().equalsIgnoreCase(artist)){
newList.add(temp.getArtist(), temp.getTitle());
}
}
return newList;
}
// return a string representation of the list
// Do not make any changes to this method!
public String toString() {
String listContent = "";
Song current = head;
...