The printTreeToTerm method

• In the Huffman encoding section of Homework 3 you are asked to print out the tree. You can do this with the printTreeToTerm method.

• The printTreeToTerm method prints a tree out on a terminal. It will look like a graphical representation of a tree rotated 90 degrees counterclockwise.

• It does this by utilizing an inorder traversal that indents on the terminal depending upon what level of the tree we are at.

• This function can be very useful in determining if your binary tree code is working correctly; simply print out the tree to find out.

• We call this method with the root of the tree and an indent of 0.

     printTreeToTerm(root, 0);
  

• Here is the code:

    // print a tree structure with horizontal indents for each level 
  
    public static void printTreeToTerm( BinaryNode t, int indent ) 
    {
      int i = 0;
      
      if ( t == null )
        return;
  
      printTreeToTerm(t.right, indent + 4);
  
      for(i=0; i<indent; i++) {
        System.out.print(" ");
      }
      System.out.println("" + t.element);
  
      printTreeToTerm(t.left, indent + 4);
    }   
  

• Suppose you had the following BinarySearchTree called bst in your program:

                          9
  		       / \
  		      /   \ 
  		     /     \ 
  		    5       11
                     / \      / \
  		  /   \    /   \
  		 4     7  10   12 
  		/                \
  	       /		  \
  	      2 	          15 
  

• If you called printTreeToTerm(bst.root, 0) your program would print this to the terminal:

                         15
                     12
                 11
                     10
            9          
                     7
                 5
                     4
  	               2
  

The BitSet Class

The Hashtable Class

• The Hashtable class implements a hashtable, which maps keys to values.

• It allows you to store an arbitrary number of arbitrary objects.

• The Java Hashtable class implements a hashtable using seperate chaining, so when a collision occurs, a single bucket stores a linked list of multiple entries, which must be searched sequentially.

• As you'll recall, one factor that affects the performance of hashing schemes is the load factor.

• In the HashTable class it is defined as the ratio of the number of occupied cells in the hash table to the size of the hash table.

• The closer the ratio gets to 1.0, the greater the chance of collisions.

• The Hashtable class has three constructors.

• The no arguments contructor will create an empty Hashtable with a default capacity of 101 elements and a default load factor of .75. This can be done as follows:

      table = new Hashtable();
  

• When the number of occupied slots in the Hashtable becomes more than the capacity times the load factor, the table will automatically grow larger.

• The Hashtable class also provides a contructor that takes one argument specifying the capacity and a constructor that takes two arguments specifying the capacity and the load factor respectively.

• There signatures are as follows:
  public Hashtable(int initialCapacity);
public Hashtable(int initialCapacity, float loadFactor);

• To insert an object into the hashtable you use the put method:
  public synchronized Object put(Object key, Object value);

  (synchronized means that only one thread may execute in the method for a given object at a time)

• This method adds a key and a value into the Hashtable.

• If there was no value in the Hashtable for the specified key, null is returned.

• If there was a value in the Hashtable for the specified key, the original value in the Hashtable is returned; this helps the program manage the cases which it intends to replace the value stored for a given key.

• If either the key or the value is null, a NullPointerException is thrown.

• The following example creates a Hashtable of numbers. It uses the names of the numbers as keys:

      Hashtable numbers = new Hashtable();
      numbers.put("one", new Integer(1));
      numbers.put("two", new Integer(2));
      numbers.put("three", new Integer(3));
  

• You should note, as you can see in the example above, only Objects can be stored in a Hashtable.

• If you want to put primitive types in (as done above) you have to wrap them in an object wrapper.

• The value can be retrieved from (or located in) the Hashtable with the following method:
  public synchronized Object get(Object key);

• This method retrieves (or locates) the value that is associated with the key specified as an argument.

• The method returns an Object reference to the value if it is located; otherwise, null is returned.

• Continuing with our example, you can retieve a number and print it out as follows:

      Integer n = (Integer)numbers.get("two");
      if (n != null) {
        System.out.println("two = " + n);
      }
  

• There is also a remove method:
  public synchronized Object remove(Object key);

• This method removes from the table the value associated with the key specified as an argument.

• The method returns an Object reference to the removed value, and null if there is no value mapped to the specified key.

• The isEmpty method returns true if the Hashtable is empty, and false otherwise.
  public boolean isEmpty();

• The method containsKey is as follows:
  public synchronized boolean containsKey(Object key);

• This method determines if the key specified as an argument is in the Hashtable (i.e., a value is associated with that key).

• If so, the method returns true, and false otherwise.

• Class Hashtable also provides a method contains to determine if the Object specified as its argument is in the Hashtable:
  public synchronized boolean contains(Object value);

• There is also a clear method that empties the Hashtable:
  public synchronized void clear();

• And there is also a size method which returns the number of keys in the Hashtable:
  public int size();

• You should consult the online Java API Specification for a full list (and descriptions) of the Hashtable methods.