Please help me implement the two search functions for BinarySearchTree.java publ
ID: 3707519 • Letter: P
Question
Please help me implement the two search functions for BinarySearchTree.java
public class BinarySearchTree<E extends Comparable<E>>
{
TreeNode<E> root;
/**
* constructor create a empty binary search tree by setting root to be null
*/
public BinarySearchTree(){
root = null;
}
/**
* Search the given data in this binary search tree
* If the data is found, return a reference to the tree node
* Otherwise, return null
* @param data The target to search
* @return a TreeNode reference to the node that contains the data
* if no node contains data, return null
*/
public TreeNode<E> search(E data){
}
/**
* Insert given node to this binary search tree. If this tree
* is empty, the given node becomes the root of this tree.
* @param newNode the given node to be inserted
*/
public void insert(TreeNode<E> newNode){
}
}
Explanation / Answer
public class BinarySearchTree<E extends Comparable<E>>
{
TreeNode<E> root;
private Comparator<T> comparator;
/**
* constructor create a empty binary search tree by setting root to be null
*/
public BinarySearchTree(){
root = null;
}
private int compare(T x, T y)
{
if(comparator == null)
return x.compareTo(y);
return comparator.compare(x,y);
}
/**
* Search the given data in this binary search tree
* If the data is found, return a reference to the tree node
* Otherwise, return null
* @param data The target to search
* @return a TreeNode reference to the node that contains the data
* if no node contains data, return null
*/
public TreeNode<E> search(E data)
{
return search_util( this.root , data );
}
private boolean search_util(TreeNode<E> r, E val)
{
if (r == null)
return false;
// if the required node is found
else if (compare(val, r.getData()) == 0)
return true;
// if the required node is smaller than current node
else if (compare(val, r.getData()) < 0)
// getLeft() return the reference to the left child
return search(r.getLeft(), val);
// if the required node is larger than current node
else
// getRight() return the reference to the right child
return search(r.getRight(), val);
}
/**
* Insert given node to this binary search tree. If this tree
* is empty, the given node becomes the root of this tree.
* @param newNode the given node to be inserted
*/
public void insert(TreeNode<E> newNode)
{
// getData() return the value of node
this.root = insert_util( this.root , newNode.getData() );
}
private TreeNode<E> insert_util(TreeNode<E> node, E data)
{
// if tree is empty
if (node == null)
// create a new node
node = new TreeNode<E>(data);
// if the dats lies in the right subtree
else if (compare(node.getData(), data) < 0)
node.setRight(insert_util(node.getRight(), data));
// if the dats lies in the left subtree
else
node.setLeft(insert_util(node.getLeft(), data));
return node;
}
}