Assignment Java Binary Search Trees

Task1

1. Complete the method named mirror() that alters the tree so that the final tree is a mirror image of the original tree. For example, if we use this method on the tree shown on the left, we end up with the tree shown on the right.

2. Write the insertM(), deleteM() and searchM() methods to insert, delete and search for an element in the mirror tree.

3. Write the inOrderM(), preOrderM() and postOrderM() methods to traverse the mirror tree. Make sure that the output of each method matches the output of the same method on the original tree.

Example: OriginalTree.inOrder() has the same output as

MirrorTree.inOrderM() which is 1 3 4 6 7 8 10 13 14

4. Add a method deleteMin() to delete the element with the minimum value.

5. In an application class check if all new methods are working properly.

--------------------------------------------------------------------------------------------------------------------------

Task2

Implement a class named Performers that displays of the top ten performers in a video game in ascending order. Each performer has a name and score. Here is an example of such performers. JediMaster 95, G-Man 99, Whiz 105, Spike 120.

Use a class based on MyBST. The class should have:

- a constructor that sets up an empty tree,

- a void insert(String name, int score) method that adds a name and a score pair to the tree.

The tree should have a maximum size of 10. After the tree has 10 elements, an attempt to add a name with a score that is less than or equal to the minimum score on the tree is ignored, and adding a score that is greater than the minimum score causes an entry with the minimum score to be dropped from the tree.

- Print the list of performers sorted by score.

--------------------------------------------------------------------------------------------------------------------------

Here's the original Binary Search Tree code:

//BinarySearchTree.java

public class BinarySearchTree {

/** * @param args the command line arguments */ public static void main(String[] args) { // Create a BST MyBST tree = new MyBST(); tree.insert("George"); tree.insert("Michael"); tree.insert("Tom"); tree.insert("Adam"); tree.insert("Jones"); tree.insert("Peter"); tree.insert("Daniel"); // Traverse tree System.out.print("Inorder (sorted): "); tree.inOrder(); System.out.print(" Postorder: "); tree.postOrder(); System.out.print(" Preorder: "); tree.preOrder(); System.out.print(" The number of nodes is " + tree.getSize()); System.out.print(" Is Peter in the tree? " + tree.search("Peter")); } }

//MyBST.java

import java.util.*;

public class MyBST>implements Tree{ TreeNode root; int size; @Override public boolean search(E element) { TreeNode current = root; // Start from the root while (current != null) { if (element.compareTo(current.element) 0) { current = current.right; // Go right } else // Element matches current.element return true; // Element is found } return false; // Element is not in the tree }

@Override public boolean insert(E element) { TreeNode current = root; if (root == null) root = new TreeNode(element); else { // Locate the parent node current = root; TreeNode parent=current; while (current != null) { if (element.compareTo(current.element) 0) { parent = current; current = current.right; } else return false; // Duplicate node not inserted } // Create the new node and attach it to the parent node if (element.compareTo(parent.element)

@Override public void preOrder() { preOrder(root); }

@Override public void postOrder() { postOrder(root); } @Override public int getSize(){ return size; } @Override public boolean isEmpty(){ return root == null; } @Override public void clear(){ root = null; size = 0; } public void inOrder(TreeNode node) { if (node== null) return; inOrder(node.left); System.out.print(node.element + " "); inOrder(node.right); } public void preOrder(TreeNode node) { if (node == null) { return; } System.out.print(" " + node.element + " "); preOrder(node.left); preOrder(node.right); } public void postOrder(TreeNode root) { if(root != null){ postOrder(root.left); postOrder(root.right); System.out.print(" " + root.element + " "); } } @Override public boolean delete(E e){ /** * Delete an element from the binary search tree. Return true if the element * is deleted successfully Return false if the element is not in the tree */ // Locate the node to be deleted and also locate its parent node TreeNode parent = null; TreeNode current = root; while (current != null) { if (e.compareTo(current.element) 0) { parent = current; current = current.right; } else break; // Element is in the tree pointed by current }

if (current == null) return false; // Element is not in the tree

// Case 1: current has no left children if (current.left == null) { // Connect the parent with the right child of the current node if (parent == null) { root = current.right; } else { if (e.compareTo(parent.element)

while (rightMost.right != null) { parentOfRightMost = rightMost; rightMost = rightMost.right; // Keep going to the right }

// Replace the element in current by the element in rightMost current.element = rightMost.element;

// Eliminate rightmost node if (parentOfRightMost.right == rightMost) parentOfRightMost.right = rightMost.left; else // Special case: parentOfRightMost == current parentOfRightMost.left = rightMost.left; }

size--; return true; // Element deleted } }

//Tree.java

public interface Tree { public boolean search(E e); public boolean insert(E e); public boolean delete(E e); public void inOrder(); public void preOrder(); public void postOrder(); public int getSize(); public boolean isEmpty(); public void clear(); }

//TreeNode.java

public class TreeNode { E element; TreeNode left; TreeNode right; public TreeNode(E o) { element = o; } }

--------------------------------------------------------------------------------------------------------------------------

To Include:

- The completed MyBST class with the new methods commented,

- The performers class, the performersDemo class and MyBSTDemo class.

Thank you.

8 8 10 10 14 6 1 6 14 7 (13 3 74 Original tree Mirror tree 8 8 10 10 14 6 1 6 14 7 (13 3 74 Original tree Mirror tree