Question: public class BinaryTree { private T data; private BinaryTree parent; private BinaryTree left; private BinaryTree right; public BinaryTree() { parent = left = right =
public class BinaryTree
{
private T data;
private BinaryTree parent;
private BinaryTree left;
private BinaryTree right;
public BinaryTree()
{
parent = left = right = null;
data = null;
}
public void makeRoot(T data)
{
if (!isEmpty())
{
System.out.println("Can't make root. Already exists");
}
else
this.data = data;
}
public void setData(T data)
{
this.data = data;
}
public void setLeft(BinaryTree tree)
{
left = tree;
}
public void setRight(BinaryTree tree)
{
right = tree;
}
public void setParent(BinaryTree tree)
{
parent = tree;
}
public T getData()
{
return data;
}
public BinaryTree getParent()
{
return parent;
}
public BinaryTree getLeft()
{
return left;
}
public BinaryTree getRight()
{
return right;
}
public void attachLeft(BinaryTree tree)
{
if (tree==null) return;
else if (left!=null || tree.getParent()!=null)
{
System.out.println("Can't attach");
return;
}
else
{
tree.setParent(this);
this.setLeft(tree);
}
}
public void attachRight(BinaryTree tree)
{
if (tree==null) return;
else if (right!=null || tree.getParent()!=null)
{
System.out.println("Can't attach");
return;
}
else
{
tree.setParent(this);
this.setRight(tree);
}
}
public BinaryTree detachLeft()
{
if (this.isEmpty()) return null;
BinaryTree retLeft = left;
left = null;
if (retLeft!=null) retLeft.setParent(null);
return retLeft;
}
public BinaryTree detachRight()
{
if (this.isEmpty()) return null;
BinaryTree retRight = right;
right =null;
if (retRight!=null) retRight.setParent(null);
return retRight;
}
public boolean isEmpty()
{
if (data == null)
return true;
else
return false;
}
public void clear()
{
left = right = parent =null;
data = null;
}
public BinaryTree root()
{
if (parent == null)
return this;
else
{
BinaryTree next = parent;
while (next.getParent()!=null)
next = next.getParent();
return next;
}
}
public static void preorder(BinaryTree t)
{
if (t!=null)
{
System.out.print(t.getData()+"\t");
preorder(t.getLeft());
preorder(t.getRight());
}
}
public static void inorder(BinaryTree t)
{
if (t!=null)
{
inorder(t.getLeft());
System.out.print(t.getData() + "\t");
inorder(t.getRight());
}
}
public static void postorder(BinaryTree t)
{
if (t!=null)
{
postorder(t.getLeft());
postorder(t.getRight());
System.out.print(t.getData() + "\t");
}
}
}
//Binary Search Tree class
//uses the Binary Tree class
public class BinarySearchTree>
//you are using the compareTo method on objects of type T; hence T should extend Comparable
{
private BinaryTree tree;
private int size;
public BinarySearchTree()
{
tree = new BinaryTree();
size=0;
}
public BinaryTree getTree()
{
return tree;
}
public boolean isEmpty()
{
return tree.isEmpty();
}
public int size()
{
return size;
}
public BinaryTree search(T key)
{
BinaryTree t = tree;
if (isEmpty()) return null;
while (t!=null)
{
if (key.compareTo(t.getData())
Step 1: Start by writing a basic client program BinaryScarchTreeDemo.java with the following skeletal structure: public class BinarySearchT reeDemo f public static void main (String[] args) //create an empty binary search tree of Integer object Step 2: To the Binary Search Tree class, add an instance method called findMax0 that returns the largest key in the binary search tree. public T findMax() Note: The largest key is the rightmost node. Step 3: To the Binary Search Tree class, add an instance method called findMin0 that returns the smallest key in the binary search tree. public T findMin) . Note: The smallest key is the leftmost node. Step 4: The binary search tree class implements the search algorithm in a non-recursive manner. Implement a recursive search algorithm. Here's the outline of the solution: //driver method public BinaryTree t = t.getLeft();
else if (key.compareTo(t.getData())>0)
t = t.getRight();
else // key is found
return t;
}
return null;
}
public void insert(T item)
{
BinaryTree newNode = new BinaryTree(); //sets left, right, parent and data to null
newNode.setData(item);
if (size==0){tree = newNode; size++;return;}
BinaryTree t = tree;
boolean done = false;
while (!done)
{
int c = item.compareTo(t.getData());
if (c==0)
{
System.out.println("Duplicate key. Can't insert");
return;
}
else if (c
{
if (t.getLeft()==null) //place to insert found
{
t.setLeft(newNode);
newNode.setParent(t);
size++;
done = true;
}
else
t = t.getLeft(); //otherwise go left one branch
}
else //c>0; need to go right
{
if (t.getRight()==null) //place to insert found
{
t.setRight(newNode);
newNode.setParent(t);
size++;
done=true;
}
else
t = t.getRight();
}
}
}
public BinaryTree findPredecessor(BinaryTree node)
{
if (node==null) return null;
if (node.getLeft()==null) return null;
BinaryTree pred = node.getLeft();
while (pred.getRight()!=null)
pred = pred.getRight();
return pred;
}
public void deleteHere(BinaryTree deleteNode, BinaryTree attach)
{
if (deleteNode==null) return;
BinaryTree parent = deleteNode.getParent();
if (parent == null) return;
if (attach == null)
{
if (parent.getLeft()==deleteNode)
parent.setLeft(null);
else
parent.setRight(null);
return;
}
if (deleteNode==parent.getRight())
{
parent.detachRight();
deleteNode.setParent(null);
//attach.setParent(parent);
attach.setParent(null);
parent.attachRight(attach);
attach.setParent(parent);
}
else
{
parent.detachLeft();
deleteNode.setParent(null);
//attach.setParent(parent);
attach.setParent(null);
parent.attachLeft(attach);
attach.setParent(parent);
}
deleteNode.clear();
}
public void delete(T key)
{
if (size==0){System.out.println("Can't delete. Empty tree"); return;}
BinaryTree deleteNode = search(key);
if (deleteNode==null) {System.out.println("Key not found. Can't delete"); return;}
BinaryTree hold = null;
if (deleteNode.getLeft()==null && deleteNode.getRight()==null)
{
deleteHere(deleteNode, null);
}
else if (deleteNode.getLeft()==null)
{
hold = deleteNode.getRight();
deleteHere(deleteNode, hold);
}
else if (deleteNode.getRight()==null)
{
hold = deleteNode.getLeft();
deleteHere(deleteNode, hold);
}
else
{
hold = findPredecessor(deleteNode);
deleteNode.setData(hold.getData());
deleteNode=hold;
deleteHere(deleteNode, deleteNode.getLeft());
}
size--;
}
}
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help