For this assignment we are going to be working on a specialised binary tree which has the following restrictions: We can only enter Integer objects with a value of 0 to 9. The maximum height is 10...

For this assignment we are going to be working on a
specialised
binary tree which has the following restrictions:

• We can only enter Integer objects with a value of 0 to 9.


• The maximum height is 10 (which means it can take a maximum of 1023 items)

The starter code for this assignment is given on canvas, as a Netbeans project, or as five separate Java Files. You can work in Netbeans, or use any other IDE of your choice.

The code contains the following files:

• ArraySorter.java – This defines a class that can sort an arrays of Integers using different algorithms


• BinaryTree.java – This is where the BinaryTree class is defined.


• BST.java – This is where the BST class is defined. This class uses a BinaryTree object.


• Heap.java – This is where the Heap class is defined. This class uses a BinaryTree object.


• TestClass.java – this is the main class. It has some methods that you need to uncomment and run as you work through the tasks.


• BStringBuilder.java – This class builds a string image of our binary trees. This helps you see the result of your work in the other modules. You do not need to change this class.

Data Structures with Java Assignment 2.2 Candidate Number : Enter your 6 -digit university candidate number in the spaces above. You must not enter your name anywhere in this document 27 Marks & 23% of the final grade This document takes you through all the tasks of this assessment. Read the document carefully and work through it completing all the tasks. You will write your answers in this document, save and submit this document when you have finished on Canvas. You will also submit your code. Information to help you complete the assignment is given in black. Instructions are given in green and blue. Reminders about academic malpractice are given in red. Green instructions are things you have to do in your code. There will also be a TODO annotation in the code with the same instruction. Blue instructions tell you that you need to write an answer or copy and paste your code or your results inside this document. The spaces for you to answer are shaded in blue. The work you submit must be your own work. Any attempt at academic malpractice such as plagiarism(using somebody else’s work), collusion(working with another student) or personation(getting somebody else to do your work) will be penalised according our Academic Malpractice Policy which you can find on the All Student page on Canvas. For this assignment we are going to be working on a specialised binary tree which has the following restrictions: · We can only enter Integer objects with a value of 0 to 9. · The maximum height is 10 (which means it can take a maximum of 1023 items) The starter code for this assignment is given on canvas, as a Netbeans project, or as five separate Java Files. You can work in Netbeans, or use any other IDE of your choice. The code contains the following files: · ArraySorter.java – This defines a class that can sort an arrays of Integers using different algorithms · BinaryTree.java – This is where the BinaryTree class is defined. · BST.java – This is where the BST class is defined. This class uses a BinaryTree object. · Heap.java – This is where the Heap class is defined. This class uses a BinaryTree object. · TestClass.java – this is the main class. It has some methods that you need to uncomment and run as you work through the tasks. · BStringBuilder.java – This class builds a string image of our binary trees. This helps you see the result of your work in the other modules. You do not need to change this class. You must not try to use code from the textbook or other sources on the Internet, because it is very unlikely that that code will work with our specialised binary tree. You must work on the code that is provided, and if you are having difficulty, consult your tutor. Task 4: Binary Search Trees (BST) This task tests your understanding of Binary Search Trees (BSTs) including the complexity of search operations on a BST. You do not need to write code in this task. The class BST.java implements a BST as a subclass of BinaryTree with one extra method addItem(). This method implements the AddItem operation of a BST to preserve the BST property. In TestClass.java remove the comment next to task4() in the main method and run the main method several times. This task4() method generates a random list of 8 numbers and places them in a BST and displays it. Here is an example output from the method. Random Numbers : 4 0 2 7 3 0 8 5 BST : ______________4______________ / \ ______0______ ______7______ / \ / \ 0 2__ 5 8 \ 3 Note: you can change the size of the list and the BST by changing the value n in the task4() method. Sometimes all the numbers do not appear. This is not an error. It is because the output only shows the top 5 levels of the BST. In the box below, draw the BST that will be generated if the numbers in the list above are inserted the reverse order: 5 8 0 3 7 2 0 4 (You can draw the tree using text in the same way as output of the java program, or you can draw the binary tree using software or on paper, and then copy and paste an image of it in the box.) [5 marks] Binary search trees (BSTs) are used because searching an item in a BST is very efficient compared to searching through a linked list. When we search for an item in a linked list of n items, the time needed (measured by the number of steps, is proportional n. We say that the time complexity of this operation is linear, or O(n). In the next part of this task we explore the complexity of searching for an item in a BST. Here is a linked list and two BSTs containing the same elements. LINKED LIST: 5 2 7 4 0 9 3 6 TREE 1: ______________5______________ / \ ______2______ ______7______ / \ / \ 0 __4 6 9 / 3 TREE 2: ______________2______________ / \ 0 3______ \ __5__ / \ 4 7