CS 70

Displaying the Tree Structure

In this phase, you'll implement printing for trees, so that someone can put

std::cout << "The tree is: " << myTree << std::endl;

in their code to show the tree (including its structure), which produces output that looks like

The tree is: ((-, apple, -), blueberry, (-, pie, -))

Required Output Format and Algorithm

Your printToStream() function should write your tree to the provided ostream (output stream) using the following recursive DISPLAY algorithm:

DISPLAY(subtree):
    if the subtree is empty,
        PRINT "-"
    otherwise:
        PRINT "("
        DISPLAY left subtree
        PRINT ", "
        PRINT value stored at root of this (sub)tree
        PRINT ", "
        DISPLAY  right subtree
        PRINT ")"

Note: your print function should not print any newlines (or std::endls)! Also, notice that each comma is followed by a single space character ().

  • Sheep speaking

    So, like, we should write the recursive DISPLAY algorithm as a helper function that takes a Node pointer? Right…?

  • Duck speaking

    And make it static because it doesn't need to access the overarching TreeSet data members.

  • LHS Cow speaking

    That's right!

Let's Go!

Follow the four development steps (Plan, Write Tests, Implement, Test & Fix) to write the following two functions to print trees:

  • printToStream (member function)
  • operator<< (global function)

These functions are described in the TreeStringSet Specification. The required format and printing algorithm is described above.

Since you haven't written an operator<< function before, we'll give you the code—it just calls printToStream. Here's the code you should add to treestringset.cpp:

std::ostream& operator<<(std::ostream& os, const TreeStringSet& tree) {
    tree.printToStream(os);
    return os;
}

(In your header file, this function should be declared outside the TreeStringSet class declaration.)

Helpful Hints

A Common Mistake

Students are often are so used to using << with std::cout that they forget that printToStream is supposed to write to the provided ostream parameter, not to std::cout. So be sure to use the provided ostream parameter (often named os or out) when writing your output.

Another Common Mistake

Often students are so used to writing << when they want to perform output, that they'll write something like

os << printToStream(node->left);

or

os << printToStream(os, node->left);

which doesn't really make sense. Remember that printToStream is a void function that doesn't return anything, so you can't use it as part of an expression like that. Instead, you need to call it on its own line:

printToStream(os, node->left);

Testing Print Functions

The help page for the CS 70 testing library includes a section on testing output to streams that you may find helpful when writing your test cases for these functions.

  • Bjarne speaking

    Remember that to use std::stringstream, you need

    #include <sstream>

To Complete This Part of the Assignment…

You'll know you're done with this part of the assignment when you've done all of the following:

(When logged in, completion status appears here.)