Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

NO PLAGIARISM PLEASE ALL NEE TO BE YOUR OWN WRITTEN CODE You may use any programming language you are comfortable with. I strongly recommend not

NO PLAGIARISM PLEASE ALL NEE TO BE YOUR OWN WRITTEN CODE You may use any programming language you are comfortable with. I strongly recommend not using C (C++, Java, C#,
Visual Basic are all good choices). Overview
For this assignment, you are to create a very basic Binary Search Tree (BST). It will read data from a file - which are a slightly modified version from Project #1. Once loaded, your BST can print the tree as both a sorted list and an ASCII-art tree.
You don't have to balance the tree. In fact, don't even try it yet. Though, to be honest, a red-black tree (as long as you do the left-child rotate trick when adding), isn't all that hard.
Part 1: Node Class
Interface
In recursively defined structures, like trees, all the coding (and complexity) is found in the recursive structure itself. So, for this assignment, all the logic will be found in the Node Class.
The Tree Class, which is defined in the handout below, merely starts recursion on the root.
\table[[,Node (int key, string value),Constructor.],[Node,left,],[Node,right,],[int,key,The key to find the value.],[string,value,The value that the node contains.],[string,toString(String label, int indent),Returns a string of the tree's structure. Please see below.],[\table[[void]],add(int key, string value),\table[[Adds the key to the correct position in the BST. If the key],[already exists, do nothing.]]]] Pseudocode
Your Node class should be as follows:public int keypublic Node left. . All your methods go here
end classAdding to the Tree
To add a key, you will write a recursive method that will either recurse to the left or right - depending on the key. Whenever it
can no longer recurse left or right, a new node is simply added.if key this node's key then create a new left child for this node. left.add(key, value)end if if right is null else end ifend method Creating the ASCII Tree
The method will recursively generate a string for the structure of the tree. One node will be displayed per line. In the examples
below, I'm using spaces followed by label that identifies each as either "L" for left and "R" for right. You can use spaces,
dashes, etc... You can use any size of indentation you like (2,3, etc...).
Notice that the current node "this" is concatenated before the left and right recursive calls. This is an example of an preorder
depth-first traversal.Declare String resultresult += label +": "if left isn't nullend if result += right.toString("R", indent +1)return result
End FunctionThe following could be produced by this algorithm. Your version is can look a bit different if you wish, but you must indent your
lines and (somehow) indicate which is the left and right branch. Notice that this is the point of the label field.L: (1869) Transcontinental Railroad L: (1846) Bear Flag Revolt R: (1911) California Flag officially adopted L: (1968) Intel Founded Part 2: BinarySearchTree Class
Interface
For this project, you are also to create a wrapper BinarySearchTree Class. In reality, this class doesn't do that much. The
class simply starts recursion of the root itself.
Naturally, there is some logic needed to handle an null root, but that is just a few basic if-statements.
Pseudocodeprivate Node root if root is null else end if... and so on.
end classPart 3: Input File Format
A number of test files will be provided to you for testing your code. The format is designed to be easy to read in multiple
programming languages. You need to use the classes, built in your programming language, to read the source files.
File Format
The first line of the data contains the total digits in the key. You might want to save this value -I can be used to separate the
key from the value (using the substring function found in most programming languages).Key 2, Value 2
..
Key n. Value nThe following is one of the most basic test files on the website.
File: california.txt
1947, Sacramento State
1976, Apple Founded
1869, Transcontinental Railroad
2003, Tesla Founded
1848, Gold Rush Begins
1911, California Flag officially adopted
1850, California joins the U.S.
1968, Intel Founded
Part 4: Testing
Once you have finished your code, you need to test it using some good test data. Now you can see why you wrote the ToTree
method. It is vital to verify if your methods are working correctly.
For example, if the following file is added to the Binary Search Tree.
File: halloween calories.txt
73, M&M's Fun size
60, Tootsie Pop
40, Starburst Fun Size
70, Kit Kat Snack Size
30, Laffy Taffy
80, Snickers Fun Size
50,Nerds Mini Box
77, Hershey's Milk Chocolate Fun Size
82, Almond Joy Snack Size
It will result in the following tree.
*: (73) M&M's fun size
L: (60) Tootsie Pop
L: (40) Starburst Fun Size
L: (30) Laffy Taffy
R: (50) Nerds Mini Box
R: (70) Kit Kat Snack Size
R: (80) Snickers Fun Size
L: (77) Hershey's Milk Chocolate Fun Size
R: (82) Almond Joy Snack Size
image text in transcribed

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Murach's SQL Server 2012 For Developers

Authors: Bryan Syverson, Joel Murach, Mike Murach

1st Edition

1890774693, 9781890774691

More Books

Students also viewed these Databases questions