Description
Goal: This lab will teach you about tree operations.
Part I
——————
Download the lab10.jar file from Canvas. Extract the contents of lab10.jar to your
working directory. There are three files in the contents. They are treeNode.h, tree.h, and
test.cpp.
In this lab, do NOT modify anything in treeNode.h and test.cpp. Your work is to
implement the methods in tree.h file. In the tree.h file, please implement the following
methods:
• treeBSearch(V x, TreeNode* t)
• isLeaf(TreeNode* t)
• height(TreeNode* t)
• nNodes()
• insert(V x)
After finishing the implementation, type the following command to compile the code.
g++ test.cpp
where file test.cpp tests the implementations of the methods. The execution result of
test.cpp is:
jikaili$ ./a.out
1
0
8
The Tree Looks Like:
9
/
8
\
7
/
6
/
5
\
4
/
3
\
2
The tree is rooted at node 5.
Your implementation must have the exactly same result.
Requirements and Hints:
• The tree should be sorted, the values of left subtree are smaller than the root; the
values of the right subtree are larger than the root
• When you insert a node, pretend that you are searching the value, insert the node
to the place where it falls off the tree
Wrap up
————————
Jar you C++ files and the downloaded data files into lab10.jar. Submit the completed file to
Canvas.