It's a homework problem. we need to build a method in java that clones a given binary search tree through recursion, ive looked up several examples online, the problem being that the program our instructor asked us to write was in what he called the Modern method, whereby rather than checking for null in each method, a tree is constructed using Dynamic dispatch from an Interface Node, connected to two subclasses nil(representing an empty node and the necessary methods to deal with an instance of an empty Node) and Vertex, a filled node and its affiliate methods. im confused on how to structure the recursion to clone the nodes, and construct the nodes to hold the cloned info. this being homework im obviously not looking for an answer but i really need some help with this.
interface Node<T extends Comparable<T>>
{
public int size();//return the number of values in the tree
public boolean empty();//true if tree is empty nil
public Node<T> insert(T x);// insert something into a binary search tree, return the node it was inserted into
public vertex<T> search(T x);//search for a given value and return the vertex ( filled node ) it exists in
public int depth();//returns the greatest depth of the tree
public void inorder();
//public Node<T> Attack_of_the_clones();
}
//note that insert must be used as in t = t.insert(x)
class nil<T extends Comparable<T>> implements Node<T> //empty tree
{
public int size() {return 0;}// empty node, therefore of size zero
public boolean empty() { return true; }//its and empty node, duh
public Node<T> insert(T x) { return new vertex<T>(x); }// returns a Tpe Node for inserting a given value into a node (thereby creating a
//vertex containing said inserted value)
public vertex<T> search (T x) { return null; }//RETURNS NULL IN SEARCHING FOR A GIVE VALUE BECAUSE NODES OF TPE nIL ARE INHERENTLY empty
public int depth() { return 0; }
public void inorder() { System.out.print("0");}
//public Node<T> Attack_of_the_clones() { return new nil<T>(this); }
}//end nil
class vertex<T extends Comparable<T>> implements Node<T>
{
protected T head;// the root of the tree
protected Node<T> left;//creates an instance of Node to serve as the left child of head
protected Node<T> right;
//constructor
public vertex(T h, Node<T> l, Node<T> r) { head = h; left = l; right = r; }// a constructed instance
//leaf instructor
public vertex(T h) { head = h; left = new nil<T>(); right = new nil<T>(); }//a constructed leaf
// a leaf is Tpically a node with no or null children, some consider the null nodes themselves to be leaves
//accesors so that the protected variables can be displayed
public T acHead() {return head;}
public Node<T> acLeft() {return left;}
public Node<T> acRight() {return right;}
public int size()
{
return left.size() + right.size() + 1;//recursively call size down the left and right trees to get all the nodes,
// and combine them ( +1 for the root) to get the size of the tree
}
public int depth()
{
return Math.max((left.depth()+1),(right.depth()+1));
}
public boolean empty() {return false; }//because its of class vertex and therefore not empty
public Node<T> insert(T x)
{
if (x.compareTo(head) <= 0)// go down left tree
left = left.insert(x);
else right = right.insert(x);// go right
return this;//root vertex has not changed
}//end insert
public vertex<T> search(T x)
{
int r = x.compareTo(head);
if(r==0)//go left
{
return left.search(x);//recursively call search using said node to move down tree
}
else //go right
{
return right.search(x);
}
}// end binary search
public void inorder()
{
Node<T> current_root = this;
if(current_root == null)
return;
left.inorder();
System.out.println(current_root + ", ");
right.inorder();
}//end inorder print
/*public Node<T> Attack_of_the_clones()
{
left_copy = curr_node.left.copy();
right_copy = curr_node.right.copy();
return new vertex(curr_node, left1, right1);
}*/
public vertex<T> largest(Node<T> x)
{
int left1 = largest(x.left);
int right1 = right.largest();
if(this.head > left1 && this.head > right1)
return this.root;
else
return Math.max(left1,right1);
}
}// end vertex
public class BinaryTree
{
public static void main(String[] args)
{
Node<Integer> n = new vertex<Integer>(3);
n = n.insert(4);
for(int i = 0; i < 10; i++)
{
n.insert((int)Math.random*8);
}
n.size();
n.depth();
n.inorder();
}//end main
}//end Binary Tree
BinaryTree.java:87: warning: [rawtypes] found raw type: vertex
public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());}
^
missing type arguments for generic class vertex<T>
where T is a type-variable:
T extends Comparable<T> declared in class vertex
BinaryTree.java:87: warning: [unchecked] unchecked call to vertex(T,Node<T>,Node<T>) as a member of the raw type vertex
public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());}
^
where T is a type-variable:
T extends Comparable<T> declared in class vertex
BinaryTree.java:87: warning: [unchecked] unchecked conversion
public Node<T> Attack_of_the_clones() { return new vertex(head, left.Attack_of_the_clones(), right.Attack_of_the_clones());}
^
required: Node<T>
found: vertex
where T is a type-variable:
T extends Comparable<T> declared in class vertex
3 warnings