INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS202 : DATA STRUCTURES

LAB  #06 : Binary and Binary Search Trees

Objectives:

1.        1.   Implementing recursive methods to count the number of nodes and the number of leaf nodes in a Binary tree.

2. Knowing how to implement and use  BinaryTree depthFirstTraversal methods.

3. Knowing how to  implement and use BinaryTree breadthFirstTraversal method.

4. Implementing a  method that will display the keys of a binary tree in bracketed form. 

2.      1.    Downloadables:

Download the file lab06.zip and unzip it in the ics202 main folder.  WinZip will automatically create a subfolder lab06.  After unzipping, you should have the following files:

Under the ics202 package:

• BinaryTree.java

• BinarySearchTree.java

Under the ics202.lab06 package:

• TestBinarySearchTree.java

• TestBinaryTree.java
  

2.   Task1

Open each of the above files and study it carefully to make sure you understand what each of them is doing.

3.   Task2

(a)    Implement each of the following recursive instance methods in the BinaryTree class:

(b)    A public int getCount( ) method that returns the count of the nodes in a binary tree. 

(c)    A public int leavesCount( ) method that returns the number of leaf nodes in a binary tree.

4.    Task3

Complete the  treePrinter method in TestBinarySearchTree.java as a recursive method that will display the keys of its binary tree argument in bracketed form: { LT  key RT } , where key is the key of the root node, and LT is the left subtree of the tree in bracketed form, and RT is the right subtree of the tree in bracketed form.

 

For, example, the binary tree:

will be displayed as:  { { 2 { 4 } } 10 { { 12 } 15 { 20 } } }

1.     5.    Task4

Complete TestBinarySearchTree.java as indicated in the comments in the file.

6.   Task5

Building a BinaryTree
The BinaryTree class has three constructors. These constructors can be used to build a BinaryTree:

 // Given two BinaryTrees left and right; builds a tree with obj as the root key
public BinaryTree(Object obj, BinaryTree left, BinaryTree right){
   key = obj;
   this.left = left;
   this.right = right;
}

 //builds an empty BinaryTree
public BinaryTree(){
  this(null, null, null);
}

 // Builds a leaf
public BinaryTree(Object obj){
  this(obj, new BinaryTree(), new BinaryTree());
}

 For example, to build the following binary tree:

   

 

The following statements can be used:

 BinaryTree tree;
tree = new BinaryTree(new Integer(6), new BinaryTree( new Integer(4)), new BinaryTree(new Integer(50)));
 tree.left.left = new BinaryTree(new Integer(30));
tree.left.right = new BinaryTree(new Integer(7));
tree.left.right.left = new BinaryTree(new Integer(15));
tree.right.right = new BinaryTree(new Integer(50));
tree.right.right.right = new BinaryTree(new Integer(20));

Complete TestBinaryTree.java by using  the above BinaryTree instance and  some of the code that you wrote in Task 2, 3, and 4.