Project on Trees: Binary Search Tree
We will focus our tree efforts in this class on binary trees. These are data structures for which each node has at most two children (the left sub-tree and the right sub-tree). Binary trees are powerful because they can be used to save and retrieve information quickly.
We learned earlier this year that if we simply choose to store information in an array, sorting that information later or trying to locate an individual element within the array can be time consuming - from n-squared time to at best n* log(n).
The use of trees can reduce the processing times significantly. Of course, this becomes important once the data grows substantially. Restricting the tree to be a binary tree greatly simplifies coding and implementation. The resulting structure is also easier for the user to understand.
When we use a binary tree to save and retrieve information, the term Binary Search Tree (BST) is used.
Your grade on this lesson will be driven of your ability to create, document, and demo the following program.
You must create a BST program that visually displays a Binary Search Tree that holds an integer as its data. The user must be presented with the following menu for the tree:
Binary Search Tree Menu:
- Create a new BST
- Add a node
- Delete a node
- Search for an integer value
- Report the largest integer value
- Report the smallest integer value
- Delete a BST
Your program should continuously update the BST after each selection and display the newly updated tree. You can use any graphical package you wish to display the information for the tree.
It is ok with your instructor if you work with your peers to select the same graphing scheme and share it (even share the same graphing code) as this is not a major part of the assignment. The code for the tree, and its operations, of course, cannot be shared.
Example Tree Output
So after creating the BST and putting a bunch of stuff in it, the tree display may look like this:
If you find it difficult to draw the circles around each integer node value, you may omit the circles. But some sort of directional arrowheads must be present to indicate parents versus children nodes of the tree.
YOUR TREE MUST BE DISPLAYED TOP TO BOTTOM AND NOT LEFT TO RIGHT. (Talk to your instructor if this is in any way unclear).