Question

create your own implementation of a Binary Search Tree using the following data structure:  

public class BinarySearchTreeVertex<E> {   
public E e;
public BinarySearchTreeVertex<K> parent;
public BinarySearchTreeVertex<K> left_child;
public BinarySearchTreeVertex<K> right_child;
}

Create a generic class called BinarySearchTree<E> that maintains a BST. This class contains a reference to the root of the BST and provides the functions add() and find():

public class BinarySearchTree<E>
{
public BinarySearchTreeVertex<E> root = null;
public boolean add(E e) {}
public boolean find(E e) {}
}

Create a BST that can hold Integers. Make a driver program that provides the following menu options:

1. Add Integer(s) to the tree
2. Display tree
3. Find an element
4. Exit

TESTING:

(Output should match all pics)

(Option#1 Test: 1. Add Integer(s) to the tree 2. Display tree 3. Find an element 4. Exit >>1 Enter Integer to add to tree (type 'stop') to exit >> Enter Integer to add to tree (type 'stop') to exit >> 3 Enter Integer to add to tree (type 'stop') to exit >> 10 Enter Integer to add to tree (type 'stop') to exit >> 1 Enter Integer to add to tree (type 'stop') to exit >>6 Enter Integer to add to tree (type 'stop') to exit >> 14 Enter Integer to add to tree (type 'stop') to exit >>4 Enter Integer to add to tree (type 'stop') to exit >>7 Enter Integer to add to tree (type 'stop') to exit >> 13 Enter Integer to add to tree (type 'stop') to exit >>stop 1. Add Integer(s) to the tree 2. Display tree 3. Find an element 4. Exit >>4

Solution Need in JAVA Code. Please do a Test and recheck before comment . Thanks

Answer 1

HI,

please find code below.

import java.util.*;

public class Main
{
static BinarySearchTree<Integer> mybst = new BinarySearchTree<Integer>();
// writing this globally to maintain data intact
public static void main(String[] args)
{
int userChoice;
String valueToInsert;
userChoice = menuDetails();
Scanner in = new Scanner(System.in);


if(userChoice == 1) /* to insert values to bst*/
{
while(true)
{
System.out.print("Enter integer to add to tree(type 'stop' to exit");
valueToInsert = in.nextLine();
System.out.print(valueToInsert);
if(valueToInsert.equals("stop"))
{
break;
}
else
{
mybst.add(Integer.parseInt(valueToInsert));
mybst.preOrderTraversal();
}
}
main(null);
}
else if(userChoice == 2)/* to display tree*/
{
System.out.println("displaying tree");
mybst.preOrderTraversal();
System.out.println();
  
main(null);
}
else if(userChoice == 3)/* to search element in tree*/
{
System.out.println("finding element in tree");
Scanner input = new Scanner(System.in);
System.out.println("What integer are you looking for?");
int findElem = input.nextInt();
boolean isFound = mybst.find(findElem);
System.out.println("Is"+ findElem + "In Tree?" + isFound);
}
}
static int menuDetails()
{

int userSeletion;
Scanner input = new Scanner(System.in);

/***************************************************/

System.out.println("Choose from these menu choices");
System.out.println("-------------------------\n");
System.out.println("1 - Add Integer(s) to the tree");
System.out.println("2 - Display tree");
System.out.println("3 - Find An element");
System.out.println("4 - Exit");

userSeletion = input.nextInt();
return userSeletion;
}

}
/*Create a generic class called BinarySearchTree<E> that maintains a BST.
This class contains a reference to the root of the BST and provides the functions add() and find():*/
class BinarySearchTree <E extends Comparable<E>>
{
  

private BinarySearchTreeVertex<E> root = null;
private Comparator<E> indexElement = null;

public BinarySearchTree()
{
root = null;
}
private int matchWith(E x, E y)
{
if(indexElement == null) return x.compareTo(y);
else
return indexElement.compare(x,y);
}
public boolean add(E e)
{
boolean ret = false;
root = add(root, e);
if(root!=null)
ret = true;
  
return ret;
}
private BinarySearchTreeVertex<E> add(BinarySearchTreeVertex<E> pnode, E elemtoInsert)
{
if (pnode == null)
return new BinarySearchTreeVertex<E>(elemtoInsert);

if (matchWith(elemtoInsert, pnode.e) == 0)
   return pnode;

if (matchWith(elemtoInsert, pnode.e) < 0)
pnode.left_child = add(pnode.left_child, elemtoInsert);
else
pnode.right_child = add(pnode.right_child, elemtoInsert);

System.out.println(pnode.e);
System.out.println(pnode.left_child);
System.out.println(pnode.right_child);
return pnode;
}
public boolean find(E e)
{
return find(root, e);
}
private boolean find(BinarySearchTreeVertex<E> p, E e)
{
if (p == null)
return false;
else
if (matchWith(e, p.e) == 0)
   return true;
else
if (matchWith(e, p.e) < 0)
return find(p.left_child, e);
else
return find(p.right_child, e);
}
public void preOrderTraversal()
{
//System.out.print("preOrderTraversal");
preOrderexecuter(root);
}
private void preOrderexecuter(BinarySearchTreeVertex r)
{
//System.out.print("preOrderexecuter");
if (r != null)
{
System.out.print(r+" "); // node
preOrderexecuter(r.left_child); // leftchild
preOrderexecuter(r.right_child);// right child
}
}
/*our own implementation of a Binary Search Tree using the given data structure: */
public class BinarySearchTreeVertex<E>
{
public E e;
public BinarySearchTreeVertex<E> left_child, right_child;
public BinarySearchTreeVertex<E> parent;

public BinarySearchTreeVertex(E e,BinarySearchTreeVertex<E> par, BinarySearchTreeVertex<E> l, BinarySearchTreeVertex<E> r)
{
parent = par;
left_child = l;
right_child = r;
this.e = e;
}

public BinarySearchTreeVertex(E data)
{
this(data, null, null,null);
}

public String toString()
{
return e.toString();
}
} //end of BinarySearchTreeVertex
}//end of BinarySearchTree

output attached:

Enter integer to add to tree(type 'stop' to exit5 55 Enter integer to add to tree (type 'stop' to exit7 75 null 5 7 Enter integer to add to tree (type 'stop' to exit9 97 null null 5 7 9 Enter integer to add to tree (type 'stop' to exitstop stopChoose from these menu choices 1 - Add Integer (3) to the tree 2 - Display tree 3 - Find An element 4 – Exit displaying tree 5 7 9 Choose from these menu choices 1 - Add Integer (s) to the tree 2 - Display tree 3 - Find An element 4 - Exit

5 7 9 Enter integer to add to tree (type 'stop' to exitstop stopChoose from these menu choices -- - --- --- --- --- --- - -- -- -- 1 - Add Integer (s) to the tree 2 - Display tree 3 - Find An element 4 - Exit displaying tree 5 79 Choose from these menu choices - --- 1 - Add Integer (s) to the tree 2 - Display tree 3 - Find An element 4 – Exit finding element in tree What integer are you looking for? Is5In Tree?true
thanks,

kindly upvote.