CRICOS Data Structures and Algorithms Trees

Data Structures and Algorithms TreesPage 1 of 3

CRICOS Provide Code: 00301J

Note:

• DSATreeNode has already been written for you, but you’ll need to understand and test it.

• The code for find() was already implemented for you - insert() anddelete() are very similar. The methods must all use the recursive approachesand pseudocode from the lecture slides.

• You may want to leave delete() until you finish the rest of the practicaland then come back to it.

Trees

Updated: 20th July, 2023

Aims

• To implement a binary tree.
• To traverse a tree.

Before the Practical

• Read this practical sheet fully before starting.
• Ensure you have completed either Practical 3 or Practical 4.

Activities

1. Binary Search Tree ImplementationFollowing the lecture slides as a guide, implement a Binary Search Tree using aDSATreeNode and DSABinarySearchTree class.

2. Implement Additional MethodsThe lecture 代 写CRICOS  Data Structures and Algorithms Trees slides described the approach for doing min(), max() and height(). Implement each of these operations in DSABinarySearchTree.Data Structures and AlgorithmsTreesPage 2 of 3

CRICOS Provide Code: 00301J

Note: Approaches can include comparing left and right heights or comparingpotential and actual leaf nodes.

Note: You may want to export the output of each traversal method as a queueor linked list, which can then be iterated over to display the contents.Now consider how you would give a percentage score for how balanced the tree is.mplement this approach as a new method called balance().

3. Implement Traversal Methods

The lecture slides described the approach for doing inorder(), preorder() and postorder()traversals of a tree. Add recursive implementations of these algorithms insideDSABinarySearchTree to output the traversed tree.

4. Interactive Menu for DSABinarySearchTree

Setup an interactive menu system to explore building a binary tree from scratch.Include at least the following options:

(a) Add node

(b) Delete node

(c) Display the tree - ask the user if they want inorder, preorder or postorder traversal

Submission Deliverable

• Your code are due 2 weeks from your current tutorial session.– You will demonstrate your work to your tutors during that session– If you have completed the practical earlier, you can demonstrate your workduring the next session

• You must submit your code and any test data that you have been using electron

ically via Blackboard under the Assessments section before your demonstration.– Java students, please do not submit the *.class filesData Structures and Algorithms

TreesPage 3 of 3CRICOS Provide Code: 00301J

Marking Guide

Your submission will be marked as follows:

• [6] Your DSABinarySearchTree and DSATreeNode are implemented correctly.
• [4] You have implemented and tested your methods for min(), max(), height()and balance().

• [6] You have implemented and can demonstrate your methods for inorder(),preorder() and postorder().

• [4] You have an interactive menu for the tree operations.

End of Worksheet