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, -))

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 below.

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 ")"

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

  • Sheep speaking

    So 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!

Testing Print Functions

In Assignment 3 (Quinn's Train), you tested printed output using std::stringstream. Go back and look at the testing code from that assignment to see how it was done.

  • Bjarne speaking

    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.)