Universidad Carlos III de Madrid

Teaching the student how to implement and use binary trees.

This exercise will use the recursive definition of a Binary Tree in order to design a Java class that implements such Binary tree. According with the definition, a Binary Tree can be both empty or consisting of a root element and, at most, two child trees (left and right).

Student's training in the use of insertion methods for inserting and deleting in binary trees.

Given a integer binary tree, implement two methods that allow inserting a subtree into the tree and to extract a subtree from it.

To practice the tree traversals over binary trees.

Given the BTree binary tree from the previous exercise, program all tree-traversals (Pre-Order, In-Order, Post-Order) that allows to make the tree traversals recursively.

To study in depth the use of tree data structures.

Given a binary tree, BTree, implement a method that returns its height.

To study in depth the use of tree data structures.

Given a binary tree, BTree, implement a method that returns the number of nodes that it has.

Teaching the student how to use binary trees.

In this exercise, you must use the BTree and BNode classes that you have programmed previously. You must implement the TongueTwister class, whose main method should build a binary tree according to the next structure:

               Tres
                |
       --------------------
       |                  |
    tristes             tigres
       |
  ------------
  |          |
  |          |
comían     trigo

To study another kind of more generic trees than binary ones, by proposing an application example: file systems. The students are supposed to learn how to generalize the operations with binary trees in order to apply them to the case of N-ary trees.

Up to now we have been working with binary trees, but they are not the only kind of trees we can find. Sometimes we need more flexible trees that allow us to have, for each node, N children nodes, where N has not to be exactly two and can be a different value for each node. This data structure is known as N-ary tree, and it is shown in Figure 1. As you can see, each tree node contains a reference to the information stored in it (info), as well as a set of references to the children nodes (children). In order to access every tree node we just need a reference to the root node (root), as in the case of binary trees.

Figure 1.  Graphical representation of a N-ary tree

In this exercise we are going to see an example in which N-ary trees are necessary: file systems. Let's suppose that we have the following file system (also known as directory tree):

C:
 |_Program Files
   |_Eclipse
   |_Java
 |_My Documents
   |_Images
   |_Music
   |_Videos
 |_ProgSis
   |_Project
     |_Module1
     |_Module2

As its name suggests, every directory or folder (in our case we are going to simplify the problem by ignoring the files) is stored following a tree structure: there is a root folder (C:) which contains many folders, each one of the containing many more and so on. In order to create and manage a file system, we are going to take the generic data structure shown in Figure 1, and we are going to make it specific to the case we are studying. The nodes in the image will be our folders. Each folder will be represented by an object of the Folder class. This class has two attributes:

In order to represent the file system, we will use the FileSystem class, which plays the role of tree since it is in charge of storing the reference to the root folder (root attribute of type Folder).

Figure 2 represents the sample file system shown before by using the Java objects we will be dealing with during the exercise.

Figure 2.  Graphical representation of a file system modeled with Java objects

In order to make the exercise easier, we provide part of the Folder class, as well as the structure of the FileSystem class. Both files can be downloaded from the following links:

First of all you will practice the use of Vector objects (if you do not know how to use them, check the API). In order to do that you have to implement the following methods of Folder class:

Before we move on, make sure that the methods you just implemented work as expected. In order to do that, create a FileSystemTest.java class and check if they behave as supposed to.

Once we have clear how Folder objects behave and how to traverse an object of Vector class, we can start dealing with the file system itself. You have to implement the following methods of the FileSystem class (besides making the necessary tests in order to check the proper working of each one with the FileSystemTest class you created earlier):

To study a possible application of binary trees to solve simple expressions.

An expression is a particular combination of operators and operands that are evaluated to obtain a particular result. The most popular way to write an expression is one that is known as "infix" in which the order of the previous combination is as follows: first operand, operator and second operand. Next, an example of an infix expression is shown (without parentheses to be easier to understand).

a-b*c+d

However, there is another kind of notation of the previous expression, known as "postfix" in which, the order of the combination changes: first operand, second operand and operator, that is, the operator is located at the end of the combination. According to this rule, the initial infix expression is transformed in the next equivalent postfix one:

abc*-d+

Postfix expressions have many advantages when subsequent processing as, for example, they don't require the use of parentheses to be evaluated and this can be performed by simple algorithms as will be seen in this problem. Having in mind that any infix expression has its equivalent postifx one, this fact provides a great flexibility and agility when trying to set up and solve the problem of evaluation of expressions.

Another major advantage of postfix expressions is that they can be represented as an Abstract Syntax Tree (AST). An AST is a binary tree whose leaves contain the same characters from the operands (a, b, c, d. ..) and the remaining nodes contain the characters from the operators (+,-,*,/). The AST binary tree of the former postfix expression is as follows:

Using this representation of the postfix expression as an AST binary tree, the evaluation of it is reduced to make a simple recursive POSTORDER traversal algorithm and using an auxiliary data structure to store the intermediate results from the porcessing of the nodes in the course of it. Both for the creation and the evaluation of the AST binary tree, TWO AUXILIARY STACKS will be needed: one of binary nodes and another of decimal values(float) that will allow to create the structure of the nodes of the tree and to store the intermediate results of the operations of the evaluation of it. Finally, to evaluate numerically the expression, it will be required an aditional table that will store the numerical values of the operands of the expression, for which it will be used an auxiliary hash table.

Operator interface contains all possible operators involved in the expressions (to simplify the problem, it is only considered binary operators)

public interface Operator {

  public static final char SUM = '+';
  public static final char SUBTRACTION = '-';
  public static final char PRODUCT = '*';
  public static final char DIVISION = '/';

}

PostfixExprEvaluator class implements the previous interface and contains the associated AST binary tree expression together with the necessary data structures to create the tree and evaluate the postfix expression. In this case, they will be two auxiliary data STACKS to store both nodes and intermediate values. The class declaration is as follows:

public class PostfixExprEvaluator implements Operator {

  Node postfixASTTree = null; // The root node of the AST postfix expression tree

  Stack stackNodes = null; // Auxiliary stack to store the nodes of the AST tree

  Stack stackResults = null; //Auxiliary stack to store the intermediate results

public Object push(Object item); // Stack data on top of the stack

public Object pop(); // Unstack data from the top of the stack

Node class represents the AST tree binary node and it stores each character(char) of the postfix expression that can be either an operator(+,-,*,/) or an operand (a, b, c, d...):

class Node {
    char value = '\0'; // The character (either an operand or a operator)
    
    Node left = null;  // The reference to the left child node of the binary tree
    Node der = null; // The reference to the right child node of the binary tree

Exercise 1: Creation of the Abstract Syntax Tree (AST).

To create the AST binary tree that will store the postfix expression, a STACK of binary nodes (Node) is needed to build the binary tree as its elements are processed. The next figure shows the general process:

The process to build the AST binary tree is as follows:

• For each of the characters in the postfix expression do the following:

• • If the character is an operand(variable a, b, c, d. ..), create a new binary node without children that will contain the character and push it on the STACK.

  • If the character is an operator(+,-,*,/), create a new binary node as follows:

  • • Extract two binary nodes from the STACK.

    • • The first element popped from the STACK will be the RIGHT child of the new binary node.

      • The second element popped from the STACK will be the LEFT child of the new binary node.

    • The data that will be stored at the new binary node will be the character that represents the operator

    • Once created the new binary node, push it on the STACK.

• Finally, return the root node of the AST binary tree created which is precisely what is obtained by unstacking the only remaining binary node that is on the STACK.

Implement the following method from PostfixExprEvaluator class that permits to create the AST binary tree from a postfix expression according to the previous process:

Node createPostfixTree( String sPostfix ) throws Exception

Exercise 2: Tree Traversal and evaluation of the Abstract Syntax Tree (AST).

A postfix expression can be easily evaluated by the use of a POSTORDER tree traversal of the associated AST binary tree that has been implemented in the previous exercise. It will be also required to have two auxiliary data structures: a STACK and a DICTIONARY of data, as shown in the figure below:

Note

The DICTIONARY of data contains the integer values of operands(a,b,c,d....). To achieve this, it has been decided to use a Hashtable object that is provided by the JDK(java.util.Hashtable) and that permits to map a number of keys with its values. In this case, the key will be the operand's asociated character. To get the integer value associated to an operand, use the following method of the class where key is the associated character of it.

public Object get(Object key)  //Returns the value to which the specified key is mapped in this hashtable. 

The process for the evaluation of the AST binary tree is based on making a POSTORDER tree traversal of it performing the following process for each binary node of the tree:

1. If the node to be evaluated is an operand (a,b,c....)

   • Stack on the results' STACK the integer value of the operand that is obtained previously from the DICTIONARY of data.

2. If the node to be evaluated is a binary operator (+,-,*,/)

   • Unstack two values from the results' STACK, calculate the result of applying the operator to those values and, finally, stack the result again on the STACK.

Implement the following RECURSIVE method of the Node class that implements the POSTORDER tree traversal of the AST binary tree according to the previous process:

void processNode( Hashtable values, Stack stackResults ) throws Exception