Question

Please I need help ASAP

Java Programing: Binary Search Tree

Fully implement the BST class in Listing 25.4 (on page 961 of the 11^th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like.

Listing 25.4 BST.java

public class BST>

extends AbstractTree {

protected TreeNode root;

protected int size = 0;

/** Create a default binary tree */

public BST() {

}

/** Create a binary tree from an array of objects */

public BST(E[] objects) {

for (int i = 0; i < objects.length; i++)

insert(objects[i]);

}

@Override /** Returns true if the element is in the tree */

public boolean search(E e) {

TreeNode current = root; // Start from the root

while (current != null) {

if (e.compareTo(current.element) < 0) {

current = current.left;

}

else if (e.compareTo(current.element) > 0) {

current = current.right;

}

else // element matches current.element

return true; // Element is found

}

return false;

}

@Override /** Insert element o into the binary tree

* Return true if the element is inserted successfully */

public boolean insert(E e) {

if (root == null)

root = createNewNode(e); // Create a new root

else {

// Locate the parent node

TreeNode parent = null;

TreeNode current = root;

while (current != null)

if (e.compareTo(current.element) < 0) {

parent = current;

current = current.left;

}

else if (e.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 (e.compareTo(parent.element) < 0)

parent.left = createNewNode(e);

else

parent.right = createNewNode(e);

}

size++;

return true; // Element inserted successfully

}

protected TreeNode createNewNode(E e) {

return new TreeNode<>(e);

}

@Override /** Inorder traversal from the root */

public void inorder() {

inorder(root);

}

/** Inorder traversal from a subtree */

protected void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

System.out.print(root.element + " ");

inorder(root.right);

}

@Override /** Postorder traversal from the root */

public void postorder() {

postorder(root);

}

/** Postorder traversal from a subtree */

protected void postorder(TreeNode root) {

if (root == null) return;

postorder(root.left);

postorder(root.right);

System.out.print(root.element + " ");

}

@Override /** Preorder traversal from the root */

public void preorder() {

preorder(root);

}

/** Preorder traversal from a subtree */

protected void preorder(TreeNode root) {

if (root == null) return;

System.out.print(root.element + " ");

preorder(root.left);

preorder(root.right);

}

/** This inner class is static, because it does not access

any instance members defined in its outer class */

public static class TreeNode> {

public E element;

public TreeNode left;

public TreeNode right;

public TreeNode(E e) {

element = e;

}

}

@Override /** Get the number of nodes in the tree */

public int getSize() {

return size;

}

/** Returns the root of the tree */

public TreeNode getRoot() {

return root;

}

/** Returns a path from the root leading to the specified element */

public java.util.ArrayList> path(E e) {

java.util.ArrayList> list =

new java.util.ArrayList<>();

TreeNode current = root; // Start from the root

while (current != null) {

list.add(current); // Add the node to the list

if (e.compareTo(current.element) < 0) {

current = current.left;

}

else if (e.compareTo(current.element) > 0) {

current = current.right;

}

else

break;

}

return list; // Return an array list of nodes

}

@Override /** Delete an element from the binary tree.

* Return true if the element is deleted successfully

* Return false if the element is not in the tree */

public boolean delete(E e) {

// 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.left;

}

else if (e.compareTo(current.element) > 0) {

parent = current;

current = current.right;

}

else

break; // Element is in the tree pointed at by current

}

if (current == null)

return false; // Element is not in the tree

// Case 1: current has no left child

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) < 0)

parent.left = current.right;

else

parent.right = current.right;

}

}

else {

// Case 2: The current node has a left child

// Locate the rightmost node in the left subtree of

// the current node and also its parent

TreeNode parentOfRightMost = current;

TreeNode rightMost = current.left;

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 successfully

}

@Override /** Obtain an iterator. Use inorder. */

public java.util.Iterator iterator() {

return new InorderIterator();

}

// Inner class InorderIterator

private class InorderIterator implements java.util.Iterator {

// Store the elements in a list

private java.util.ArrayList list =

new java.util.ArrayList<>();

private int current = 0; // Point to the current element in list

public InorderIterator() {

inorder(); // Traverse binary tree and store elements in list

}

/** Inorder traversal from the root*/

private void inorder() {

inorder(root);

}

/** Inorder traversal from a subtree */

private void inorder(TreeNode root) {

if (root == null)return;

inorder(root.left);

list.add(root.element);

inorder(root.right);

}

@Override /** More elements for traversing? */

public boolean hasNext() {

if (current < list.size())

return true;

return false;

}

@Override /** Get the current element and move to the next */

public E next() {

return list.get(current++);

}

@Override /** Remove the current element */

public void remove() {

delete(list.get(current)); // Delete the current element

list.clear(); // Clear the list

inorder(); // Rebuild the list

}

}

/** Remove all elements from the tree */

public void clear() {

root = null;

size = 0;

}

}

TestBST.java Listing

public class TestBST {

public static void main(String[] args) {

// Create a BST

BST tree = new BST<>();

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("\nPostorder: ");

tree.postorder();

System.out.print("\nPreorder: ");

tree.preorder();

System.out.print("\nThe number of nodes is " + tree.getSize());

// Search for an element

System.out.print("\nIs Peter in the tree? " +

tree.search("Peter"));

// Get a path from the root to Peter

System.out.print("\nA path from the root to Peter is: ");

java.util.ArrayList> path

= tree.path("Peter");

for (int i = 0; path != null && i < path.size(); i++)

System.out.print(path.get(i).element + " ");

Integer[] numbers = {2, 4, 3, 1, 8, 5, 6, 7};

BST intTree = new BST<>(numbers);

System.out.print("\nInorder (sorted): ");

intTree.inorder();

}

}

Answer 1

In this question, TestBST.java Listing contains the main method: Object declaration of class BST(string input) then it calls insert (insertion of tree nodes), then inorder transversal, followed by postorder transversal and then preorder transversal. After transversal we need to get total no of nodes using function defined as getsize(); Then we have to get path from one node; Now we again make an object of BST class(int input) then again calling inorder transversal.

//we have to overload insert method for both string input as well as integer input for integer we just directly compare with <, > comparator but in case of string use compareTo predefined java methods

void insert(int key) {
   root = insertRec(root, key);
}
  
Node insertRec(Node root, int key) {
  
if (root == null) {
root = new Node(key);
return root;
}
  
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
  
return root;
}

@Override

public void insert(String root) {
if (this.root == null) {
this.root = root;
} else {
if (this.root.compareTo(root) < 0) {
if (this.left != null) {
this.left.addNode(root);
} else {
this.left = new BinaryStringTree(root);
}
} else {
if (this.right != null) {
this.right.addNode(root);
} else {
this.right = new BinaryStringTree(root);
}

}
}
}

void inorder() {
inorder1(root);
}

void inorder1(Node root) {
if (root != null) {
inorder1(root.left);
System.out.println(root.key);
inorder1(root.right);
   }
}

void preorder() {
    preorder1(root);
}

void preorder1(Node root) {
    if (root != null) {
       System.out.println(root.key);
        preorder1(root.left);
        preorder1(root.right);
    }
}

void postorder() {
    postorder1(root);
}

void postorder1(Node root) {
    if (root != null) {
        postorder1(root.left);
        postorder1(root.right);
       System.out.println(root.key);
    }
}

/*getsize is similar as well as path is similar only hack in this question is how to insert string because in case of BST left should be smaller than root and right should be greater than root. Further we compare it with such a way that any node in left can't be greater than root ie leaf(last node without any children) on right of predecessor is ok(ie say 4 is leaf and 2 is its current root) and if this root node is on left of another root(say 3) its fine but no this not bst as 4>3 hence unbalanced */