CPSC 215 Lab 9, 11/11/99


This lab asks you to write a number of operations on binary (search)
trees.  Be sure to write a "main" method to demonstrate your methods -
and be sure to indicate exactly what's being printed by your
demonstration.  I've provided you a template with some of the code I
wrote in class today (note since we didn't test it, there may be syntax
errors).

--------------------------------------------------------------------------

class node
{   int head;
    node left;
    node right;
    public node(int h, node l, node r)
    { head = h;  left = l;  right = r; }
} // end class node

public class trees
{
  node root;    // you might not even need this.

    // determines if x is in tree T:
    public staticboolean intree(int x, node T)
    {  if (T == null) return false;
        else if (x == T.head) return true;
         else return (intree(x,T.left) || intree(x,T.right));
    }   // end intree

    // determines if x is in *binary search* tree T
    public static boolean instree(int x, node T)
    {
	if (T == null) return false;
	 else if (x == T.head) return true;
          else if (x < T.head) return instree(x,T.left);
	   else return instree(x,T.right);
    }

    // non-recursive version of above function
    public static boolean iter_instree(int x, node T)
    {
	boolean temp = false;  // indicates if x has been found
        node current = T;
        while ((current != null) && (!temp))
        {  
	 if (x == current.head) temp = true;
	  else if (x<current.head) current = current.left;
	   else current = current.right;
        } // while
        return temp;
    } // end iter_instree;

/* --------------------------  YOUR CODE  ----------------------- */

/* 
1. Write a method

  public static void printtree(node T, String order)

  That prints out the nodes in the tree.  The order argument is a 
string that's either "in", "pre" or "post", indicating the order the
nodes should be printed.  If order is any other string, default to inorder.
Which order do you think should be used on binary search trees?

2. Write a method that returns the number of nodes in a binary tree
  
  public static int treesize(node T)

3. Write a method that returns the "depth" of a binary tree.  The depth
   is the maximum distance between a node and a root, or the total
   number of "levels" in the tree.  For complete binary trees this is 
   close to log n, but in the worst case, this can be as bad as n 
   (recall lecture).  For example, the depth of the following tree is 4,
   because the "7", the node furthest away from the root, is at the 4th 
   level.

      8
    /   \
   5     9
  / \     \ 
 3   6     10
      \
       7
----

3b.  Modify the iter_instree methods I gave you above so it returns not
whether the int is in the tree, but the depth (i.e "level") that it appears 
in.  For example, for the "6" node in the above tree you should return 2.
The root node is always at level 0.  If the int is not in the tree, your
function should return -1.

  public static int levelof(int x, node T)


4. Write code to insert a new integer into a binary SEARCH tree

  public static node insert(int x, node T) // recursive or iterative?

  The average time complexity of your function must be log n.


5. Write a method that takes a list of integers and inserts them into
a binary search tree:
  
  public static node toTree(cell L)   // I'm sure you can define cell by
now!

Print out the resulting tree with an inorder traversal.  What have you
just done?  :-)


6. Experimental Excercise:  Use the "toTree" method and the "depth"
   method, and the following function that generates random lists:

public static cell randomlist(int length)  //use large sizes - like 4096 (4K)
  { cell ax= null;
    for (int i=0;i<length;i++) 
      ax = new cell((int) (Math.random() * 99000000),ax);
    return ax;
  }

Run 5 experiments with random lists of 4096 integers, insert them into
a binary SEARCH tree, and compute the AVERAGE depth of each node in the 
tree (there won't be that many repeat ints - not enough to matter).

   **** What do the results tell you? ****

public static double averageDepth(cell L, node T) // T made from L
{  int ax = 0;
   int size = 0;
   cell current = L;
   while (current != null)
    { ax = ax + levelof(current.head, T);
      current = current.tail;
      size = size + 1; // keep track of number of ints
    }
   return ((double) ax) / ((double) size);
}

*/

public static void main(String[] args)
{  /* demonstrate your methods here */
  node A = new node(4,new node(2,null,null),
		new node(7,new node(5,null,null),null));
  // is A a binary SEARCH tree?
} // end main

} // end class nov11