Binary Tree Using Java

A tree data structure can also be incorporated into a Java application by using the TreeMap collection class that is defined in the java.util package. The TreeMap class has many member methods that are comparable to member functions that you defined in the C++ BinarySearchTree class. However, the TreeMap class is missing two methods that you used in the C++ application, the displayInOrder() and getTreeDepth() member functions. You can define your own displayInOrder() method to display keys and values stored in nodes of the tree, but there isn t any way of calculating the depth of a tree in Java. This is an implementation detail that s hidden from the end user .

At the end of this section is the Java equivalent of the C++ application presented previously in this chapter. The Java application creates a tree and places the same three keys and values on the tree and then manipulates those values the same way as the C++ application manipulated those values.

Let s see how the Java application works. It begins by declaring an instance of the TreeMap class and assigning it to the tree reference. The TreeMap class is similar to the BinarySearchTree class defined in the C++ version of this application.

The application then declares two strings to store the key and value of a node. These are initialized to NULL. The application also declares an integer to control the for loop. The for loop assigns strings to the key and value variables and then adds each key and value to the tree.

Similar to the C++ version of the application, the Java version calls the containsKey() method that is a member of the TreeMap class. This method returns a Boolean true if the key already exists in the tree; otherwise , a Boolean false is returned. As with the C++ version, the not operator is used to reverse the logic of the value returned by the containsKey() .

The put() member method of the TreeMap class places the key and value on the tree. The put() method is similar to the add() member function that you defined in the C++ version of this application. Each time a new key and value is added to the tree, the key and value are displayed on the screen, as shown here:

 Adding three keys and values into the tree. Adding node - key: 345 value: Bob Adding node - key: 123 value: Mary Adding node - key: 999 value: Sue 

Next , the displayInOrder() method is called to display the contents of the tree on the screen. The displayInOrder() method is defined at the bottom of the Java listing. Here s how it works. First the keySet() method is called to copy the contents of the tree to a key set. Think of a key set as a two-column table where one column contains keys and the other corresponding values. Each row is a node of the tree.

Next, an instance of the Iterator class is created. As you ll remember from your Java programming course, the Iterator class has member methods that enable you to move through a list such as a key set. In this example, the Iterator class returns the key of each row in the key set. The key is then passed to the get() member method of the TreeMap class to retrieve the value associated with the key. Both the key and the value are then displayed on the screen, as shown next.

 In order traversal of tree: key: 123 value: Mary key: 345 value: Bob key: 999 value: Sue 

After the contents of the tree is displayed on the screen, the application displays the size of the tree by calling the size() member method of the TreeMap class. Here s what is displayed on the screen. Remember that the size is the number of nodes on the tree.

 Size of tree before removing nodes 3 

The application then calls the get() member method to retrieve the value associated with the key 123. If the value isn t NULL, then the application displays the key and the value on the screen, as shown here:

 Retrieving a value from the tree: Found key: 999 value: Mary 

Next, the application removes the node whose key is 123 by first calling the containsKey() member method of the TreeMap class to determine if there is a node that has 123 as a key. If so, the remove() member method is called and passed the key 123 to remove the node. A message is displayed on the screen, as shown here, to indicate that the node is being removed:

 Removing a node from the tree: Removing key 999 

To show the result of the node being removed, you call the displayInOrder() method to display the contents of the tree and call the size() member method to display the size of the tree. Here s what is displayed on the screen when these methods are called:

 In order traversal of tree: key: 345 value: Bob key: 999 value: Sue Size of tree after removing nodes  2 

Here is the program that creates and manipulates the tree in Java:

 import java.lang.*; import java.text.*; import java.util.*; public class BinarySearchTreeDemo {   public static void main(String[] args)  {    TreeMap tree = new TreeMap();    String key = null;   String value = null;   int i;    System.out.println("Adding three keys and values into the tree.");  for(i=0; i<3; i++)    {    if (i==0)    {     key ="345";     value="Bob";   }    if (i==1)   {       key ="123";     value="Mary";   }    if (i==2)    {      key="999";      value="Sue";     }    if (!tree.containsKey(key))    {      System.out.println("Adding node - key: " + key + " value: "       + value);     tree.put(key, value);     }    else     {      System.out.println("Generated duplicate key: " + key);     }    }   System.out.println("\nIn order traversal of tree:");   displayInOrder(tree);    System.out.println("\nSize of tree before removing nodes: "     + tree.size());   System.out.println("\nRetrieving a value from the tree:");   value = (String)tree.get("123");   if(value != null)   {   System.out.println("Found key: " + key + " value: " + value);   }   System.out.println("\nRemoving a node from the tree:");   if(tree.containsKey("123"))    {    System.out.println("Removing key: " + key);    tree.remove("123");   }    System.out.println("\nIn order traversal of tree:");   displayInOrder(tree);   System.out.println("\nSize of tree after removing nodes: "      + tree.size());   }  private static void displayInOrder(TreeMap tree)  {   Set keys = tree.keySet();   Iterator ii = keys.iterator();    while(ii.hasNext())   {     String key = (String)ii.next();     String value = (String)tree.get(key);   System.out.println("key: " + key + "\tvalue: " + value);   }  } }