Tree Statistics
Tree performance is critically dependent on the shape of the tree. In this final development phase, you'll develop some metrics that will provide you with insight into how nodes are arranged within the tree.
For example, here is a plausible output after six insertions:
6 nodes, height 2, average depth 1.33333
Your Task…
As usual, check out the Helpful Hints section before you dive in!
Following the four steps of our development process (Plan, Write Tests, Implement, Test & Fix), implement the following member functions from the TreeStringSet class:
averageDepth()height()showStatistics(...)
These functions are described in the TreeStringSet Specification, but also described in more detail below.
Depth and Average Depth
The depth of a node is the distance from the root to that node. The root of a tree has a depth of 0; its children each have a depth of 1; its grandchildren each have a depth of 2; and so on.
The average depth can be calculated by first calculating the sum of the depths of all the nodes in the tree, and then dividing that value by the total number of nodes.
As a special case to avoid division by zero, if a tree doesn’t have any nodes, we define its average depth to be -1.
Height
The height of a tree is the longest path length from root-to-node in the tree; in other words, the depth of the deepest node. A tree with only a single node (the root) has a maximum path length of zero. Thus an empty tree has a height of -1.
Statistics Output Format
The showStatistics() member function should summarize the structural properties of a TreeStringSet object in the following format:
S nodes, height H, average depth D
Where S is the number of nodes in the tree, H is the tree’s height, and D is the average depth of the nodes in the tree.
At the end of the line of text, showStatistics() should write a newline (std::endl) character.
You have already implemented a function to get the size of a tree.
Helpful Hints
Testing Output
Don't forget that you can use a std::stringstream object to test printed output. But if you do, don't forget to include the newline at the end, so you check against "6 nodes, height 2, average depth 1.33333\n".
Printing double Values
Just use the regular << with its standard settings to print the average depth. Our tests will fail if you print using some other method that gives more or fewer decimal places than <<.
(When logged in, completion status appears here.)