COMP225 Practical Exercises for Week 5
This practical gives you some practice in programming with binary search trees. It uses the class BST which was introduced in lectures and has been slightly extended here. Download the file BST_practical.cpp which is the binary search tree class with methods for extracting subtrees. Now complete the function definition in the file height.cpp for the starred question below. When you have written the function compile using g++ BST_practical.cpp.
- Using the BST class, implement a function which takes an array of integers and builds a binary search tree.
- (*) Using the BST class introduced in lectures and extended in the file BST_practical.cpp, implement a recursive function to compute the height of a binary search tree. You may use the result of the first question to test your code.
- Tree sort is a way to sort items using binary search trees. The idea is, given an array of integers to build a binary search tree (eg using question 1) and then output the items using an inOrder traversal. Implement Tree sort from this desciption and experiment on some small examples. What is the worst-case complexity? You could try comparing experimentally with some of the other sorting methods.
Answers to all of the above starred questions should be submitted into the online system by Monday morning of Week 6. Please submit the file height.cpp, and remember to remove your "int main()..." if you use one there.