I have given you a generic binary tree class BinTree.java. It contains a method,

Question

 I have given you a generic binary tree class BinTree.java. It contains a method, makeRandomTree(int n), that creates a binary  tree of a random shape with n nodes. Each node has a "name" consisting of the step at which the node was created (i.e. 0 is the first node created, 1 the second, and so on.  The toString method prints the tree in pre-order, including the empty links.  This is enough information to re-create the tree on paper so you can see what it looks like.  I would like you to 1) write three routines, pre-order, in-order, and post-order which will print the tree in each of those ways, similar to what the toString method does.  2) write a recursive routind depth() which returns the depth of the deepest node in the tree.  The root has depth 0.  The empty tree has depth --1.  3) Write a main program that asks the user to enter two integers: n, a number of nodes, and howMany.  Over and over again, for a total of howMany times, instantiate a new tree with n nodes, find its depth, and ultimately print the depths of the shallowest, average depth, and deepest tree.  Sample run: Enter n: 10 Emter repetitions: 1000 Shallowest tree was <something around 3> Deepest tree was <something around 9> Average depth was <something> 

 GENERIC BINARY TREE GIVEN import java.util.Random;  public class BinTree<T> {   private Node<T> root;   private Random r;    public BinTree()   {     this.root = null;     this.r = new Random();   }    public void makeRandomTree(int n)   {     for (int i = 0; i < n; i++)     {       ranInsert(i);     }   }    public void ranInsert(int name)   {     Node<T> where = root;     Node<T> next = null;     boolean done = (where == null);     if (root == null)     {       root = new Node<T>(name);       return;     }     while (!done)     {       if (r.nextBoolean())       {         next = where.getLeft();         if (next == null)         {           where.setLeft(new Node<T>(name));           done = true;         }       }       else       {         next = where.getRight();         if (next == null)         {           where.setRight(new Node<T>(name));                   done = true;          }       }       where = next;     }   }         public String toString()   {     return recToString(this.root, "", 0);   }    private String recToString(Node<T> r, String soFar, int depth)   {     String retval = soFar;     if (r == null)     {       retval += "Null ";     }     else     {       retval += r.getName() + " ";       retval = recToString(r.getLeft(), retval, depth + 1);       retval = recToString(r.getRight(), retval, depth + 1);     }     return retval;   }    public class Node<R>   {     private R value;     private Node<R> left;     private Node<R> right;     private int name;      public Node(int n, R val, Node<R> lft, Node<R> r)     {       this.name = n;       this.value = val;       this.left = lft;       this.right = r;     }      public Node (int n, R val)     {       this(n, val, null, null);     }      public Node (int n)     {       this(n, null, null, null);     }      public Node ()     {       this(0, null, null, null);     }      public R getValue()     {       return this.value;     }      public int getName()     {       return this.name;     }      public Node<R> getLeft()     {       return this.left;     }        public Node<R> getRight()     {       return this.right;     }      public void setLeft(Node<R> lft)     {       this.left = lft;     }      public void setRight(Node<R> r)     {       this.right = r;     }   }    public static void main(String args[])   {     BinTree<Integer> bt = new BinTree<Integer>();      bt.makeRandomTree(Integer.parseInt(args[0]));     System.out.println(bt);   } }             

Explanation / Answer

private String inorder(Node<T> r,String soFar, int depth){
   String retval = soFar;
   if (r == null)
       retval += "Null ";
   else{
       retval = inorder(r.getLeft(), retval, depth + 1);
       retval += r.getName() + " ";
       retval = inorder(r.getRight(), retval, depth + 1);
   }
   return retval;
}

private String preorder(Node<T> r,String soFar, int depth){
   String retval = soFar;
   if (r == null)
       retval += "Null ";
   else{
       retval += r.getName() + " ";
       retval = preorder(r.getLeft(), retval, depth + 1);
       retval = preorder(r.getRight(), retval, depth + 1);
   }
   return retval;
}

private String postorder(Node<T> r,String soFar, int depth){
   String retval = soFar;
   if (r == null)
       retval += "Null ";
   else{
       retval = postorder(r.getLeft(), retval, depth + 1);
       retval = postorder(r.getRight(), retval, depth + 1);
       retval += r.getName() + " ";
   }
   return retval;
}

private int depth(Node<T> r){
   if (r == null)
       return 0;
   int l_h = depth(r.getLeft());
   int r_h = depth(r.getRight());
   return Math.max(l_h,r_h) + 1;
}

public static void main(String args[]){
   Scanner sc = new Scanner(System.in);
   System.out.print("Enter n : ");
   int n = sc.nextInt();

   System.out.print("Enter repetitions : ");
   int r = sc.nextInt();
   int min_h = Integer.MAX_VALUE;
   int max_h = Integer.MIN_VALUE;
   double avg_h = 0.0;
   for (int i = 0; i < r; i++){
       BinTree<Integer> bt = new BinTree<Integer>();
       bt.makeRandomTree(n);
       int h = depth(bt.root);
       min_h = Math.min(min_h,h);
       max_h = Math.max(max_h,h);
       avg_h += h;
   }
   System.out.println("shallowest tree was : " + min_h);
   System.out.println("Deepest tree was : " + max_h);
   System.out.println("Average depth was : " + (avg_h/r));
}


add this code to above file, make to sure replace the main function with the updated one

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.