HL Mastery aspect:

Binary Tree ADT

Visit left subtree
output data
visit right sub-tree

On this page: [ traversal | trees and maths | exercises ]

Traversing a binary tree

Means visiting all of its nodes; consider the tree below:

One way to traverse the tree is to trace out the outline of the tree as shown by the dotted line. If you read out the names as you pass underneath each node you will have read them out in alphabetical order.

This is known as inorder traversal of the tree and is carried out by this method:

  /**
   * Inorder traversal of the tree
   *
   * @param n - the currently processed Node
   */
   public void displayTreeInOrder(Node n)
   {
     if (n != null)
     {
       displayTreeInOrder(n.getLeft());
       display.append((String) n.getData() + "\n");
       displayTreeInOrder(n.getRight());
     }
   }

A binary tree can also be used to hold a mathematical expression:

If you traverse this tree inorder you get: (2 + 3) * 4. Brackets can be put around each subtree and, in this case, are neccessary.

Back to top

Exercises

Implement a tree Applet that can store arithmetic expressions. Use the String split() or other method to take an arithmetic expression, such as "9 + (3 * 3) - (9 / 3)" and insert the elements in the correct position of an ordered tree.

Note that the root element should be an arithmetic operator near the middle of the String. You will need some tricky coding to figure out how many elements you get. An alternative approach is to investigate the java.util.StringTokenizer Class.

Another use for the StringTokenizer might be to build an ordered list of words from a text file. Duplicate words should not be added.

This could be the basis for several interesting projects - eg a spell-checker or a program that lists, alphabetically, all the identifiers and methods in a given Java source file.

You could store word counts in the node with the words to analyse a text file to locate the most commonly used words. Perhaps you could even compare two text files for similarity on this basis - a plagiarism detector.

Related: [ Java home | Data structures home | Previous: trees ]

We will consider trees from a logical point of view and discuss arithmetic expressions on the theory pages (link to come).

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.