Lab Assignment 25 (Binary Search Trees)

1.Write a Java project named Lab25A that will create our own tree node class and use it to build a binary search tree.

Create a secondary class named TreeItem with the following:

i.3 instance variables:

1.An integer value

2.Two TreeItem variables: left and right

ii.A constructor that receives an integer parameter. It should fill the integer instance variables and set the TreeItem variables to null.

iii.An int method that returns the value of the integer instance variable

iv.A String method named toString that returns a string with the integer instance variable (and a label).

Create another new class named BinarySearchTree with the following:

i.An instance variable named root (data type TreeItem)

ii.A constructor with no parameters that sets root equal to null

iii.A boolean method that

1.Receives one integer parameter

2.Inserts the integer parameter value in the tree

3.Use the “Inserting an Element to a Binary Tree” code in the PowerPoint notes to guide you.

4.Remember that our tree node data type is called TreeItem, not TreeNode, so you’ll need to change a few things

iv.A boolean method that

1.Receives one integer parameter and the TreeItem root

2.Searches for that value in the tree

3.Returns a true if it is found and false otherwise

4.Use the “Searching an Element in a Binary Search Tree” code in the PowerPoint as a guide.

v.A void method that

1.Uses the inorder algorithm to look at every node in our tree

2.It should print the value of all nodes and how many children they have. (They will have 0-2 children depending on whether left or right are null.)

3.If you go to the “BST Class” slide in the PowerPoint and click on the green box, it will show you code for BST. You can look at the 2 inorder methods there to get an idea of how to do this.

Back in the main method of the main class:

i.Create a new BinarySearchTree object

ii.Read a set of values from the text file (Lab25A.txt) and use the tree’s insertion method to place them in the tree

iii.Ask the user for an integer and call the tree’s searching method to see if it is in the tree.

iv.Call the tree’s void method to print all the node values and number of children.

You will also need to create a diagram in PowerPoint, Word or some other program to show what your tree will look like based on the values inserted and the order they were added. Name this file Lab25A_Diagram.

2.Write a Java project named Lab25B that will create a BinarySearchTree tree of string values and use the methods to fill and print it.

Make TreeItem and BinarySearchTree classes and copy the code from Lab25A into them

i.In the TreeItem class change the int instance variable to be a String variable and make any changes necessary to the methods to handle this new data type.

In the BinarySearchTree class

i.Add a new int instance variable named size and set it = 0.

ii.Increase size by 1 every time you insert a new node.

iii.Go to the “BST Class” slide in the PowerPoint and click on the green box see the code for code for BST.

iv.Copy all of the inorder, preorder and postorder methods into your BinarySearchTree class. (Don’t copy the @Override lines above them.)

v.Adapt the methods to work with the TreeItem class instead of TreeNode

vi.Add an int method with no parameters that returns size.

In the main method:

i.Create a new BinarySearchTree tree

ii.Read integer values from the text file (Lab25B.txt)

iii.Add each value to the tree

iv.After adding all the values, print the size of the tree (using the new function)

v.Print the tree inorder, preorder & postorder. Make sure to state which order you are printing for each one.

You will also need to create a diagram to show what your tree will look like based on the values inserted and the order they were added. Name this file Lab25B_Diagram.

This week we will be learning about Binary Search Trees in Chapter 25. This is a data structure like the linked list, but instead of a single link to the next node in the structure, each node will have a link to a right child node and a link to a left child node, thus forming a “tree”. Binary search trees have rules that must be followed when inserting new data, so that the tree always keeps its data in a sorted format.