LAB 5— Binary Search Tree ADT, Due Friday March 14th at 23:59.

Remark: late submissions wont be marked.

Problem Statement.

In this assignment you are required to implement a referenced based binary search tree ADT with insertion and preorder, postorder and inorder traversal operations. Your program must read a list of strings from an input file and insert them into the binary search tree. Then it must traverse the tree in preorder, inorder and postorder manner and print the data in the tree on the screen.

Input file:

The program has one input file called “data.txt” that contains a string on each line. There is no repetitive string in the file. Below is a sample:

NewYork
Cairo
Toronto
Barcelona
London
Paris
Rome
Athens
Venice

Output:

Your program must read each string from the input file and insert it into a binary search tree ADT, then it has to print the contents of the tree in three ways: preorder, inorder and postorder (notice the order of traversals is important).

For instance the output of your program for the above input must be.

Preorder Traversal:
NewYork
Cairo
Barcelona
Athens
London
Toronto
Paris
Rome
Venice

Inorder Traversal:
Athens
Barcelona
Cairo
London
NewYork
Paris
Rome
Toronto
Venice

Postorder Traversal:
Athens
Barcelona
London
Cairo
Rome
Paris
Venice
Toronto
NewYork

 

Implementation.

You need to implement reference based implementation of the binary search tree (BST) ADT and this time you must use java generics in your implementation.  First you need to declare a class TreeNode for the nodes of the BST ADT. Bellow is a possible implementation

public class TreeNode<T> {

  private T item;

  private TreeNode<T> leftChild;

  private TreeNode<T> rightChild;

 

  public TreeNode(T newItem) {

    // Initializes tree node with item and no children (a leaf).

    item = newItem;

    leftChild  = null;

    rightChild = null;

  }  // end constructor

   

  public TreeNode(T newItem,

                  TreeNode<T> left, TreeNode<T> right) {

    // Initializes tree node with item and

    // the left and right children references.

    item = newItem;

    leftChild  = left;

    rightChild = right;

  }  // end constructor

 

  public T getItem() {

    // Returns the item field.

    return item;

  }  // end getItem

  public void setItem(T newItem){
    item = newItem;
  }

  //implement methods for getLeftChild, setLeftChild , getRightChild, and setRightChild.

}

Now the BST ADT is a class with the following structure:

public class BSTreferencedBased <T>{
   private TreeNode<T> root;
   public BSTreferencedBased(T newItem){
      root = new TreeNode<T> (newItem);  //creates a BST with one node.
   }
   public BSTreferencedBased(){
     root = null;  //creates an empty BST
   }

   public void insert( T newItem){
     if (root == null){
        root = new TreeNode<T> (newItem); 
     }
     //implement the rest here.
   }

   public void preorder() {
     //implement preorder traversal here
   }
   public void inorder() {
     //implement inorder traversal here
   }
   public void postorder() {
     //implement postorder traversal here
   }

}

 Name the main class (the class with the main function) bst.java.

Standards (very important): your program must follow the exact output and input specifications mentioned above. The name and the format of the input file, the format of the output, and the name of the main class must follow the above mentioned rules . Failing to comply to the standards will result in up to 50% penalty.

Style: part of the grade is for having proper style which includes proper indenting and having enough comments.

Submission: zip all your source files (DO NOT SUBMIT THE .class or .exe files) and submit it through submission server submit.cs.sfu.ca. The submission server only accepts the zipped files. You can zip your assignment files using the winzip program or the zip, gzip linux command, DO NOT SUBMIT RAR FILES. Include your name and student number in your source file that includes the main function.

Remark: there will be four submission groups for each lab assignment make sure you submit to the group that you belong to (if you are registered in the first lab submit to the first group, and so on) otherwise there will be a 50% penalty.

Implementation Language: The programming problems in assignments, can be written in either JAVA or C++. It’s not necessary to learn JAVA for those who know only C++ and to learn C++ for those who know only JAVA.

---