CSE326 Assignment #2
Spring 2002

Due: Friday, April 19, 2002, at the beginning of class.
  Electronic turn-in due by 5:30 PM

This assignment has both programming and written parts

Reading in Lewis & Denenberg:

• Section 4.1, 4.2, 4.3, 4.4, 6.2

Programming

1. Get projects/remove.tar.gz from the course directory.

2. Learn to use tree (see the tutorial, below).

3. When removing a node with two children, one has a choice of replacing the node with either its successor or its predecessor. Which does tree do? Put the answer in your README.

4. In main.C, implement TreeNode::Remove() the same way as tree does, i.e., use the same choice of successor vs. predecessor. It's not necessary for your program to highlight and emphasize nodes in the same way, but it sure looks pretty.

5. The TreeNode::PrintCompact method in main.C is called in response to a print command. Implement in-order and post-order printing, with output format exactly the same as what tree does.

6. Extra-Credit:Add a level traversal printout (see page 108 in the textbook for a definition). Any reasonable output format is fine.

7. Turn in your assignment electronically, before the due-date. See Turnin Info for how to turn in; the project name is remove.

Problems

From Chapter 11:

• 3, 5, 17, 20, 21, 25, 36, 37.

• Extra-Credit: 19, 29.

1. There is a program tree in the course bin/ directory. Run it; the command line should respond like this:

        $ tree
        1>
   

   In addition, a window called something like 326 Visualizer will appear. Arrange your windows so that you can both type into your command line, and watch the visualizer.

2. tree is a command-driven program, just like your shell. Type help to see a list of tree commands.

        1> help
        Commands:
          +       : find a node, inserting if it's not found.
          -       : remove a node (if it's in the tree).
                .
                .
        2>
   

   tree is for playing around with binary search trees; finding and removing nodes are the most useful commands. Insert and remove few nodes:

        2> +10 +6 +14 +7 +5 -6 -2 +3
        3>
   

   (it doesn't matter whether you type a bunch of commands at once, or only one at a time). Note that the visualizer animates the insertions. The pause for each step can be controlled with the delay command; for example

        3> delay 250
        4>
   

   to make things move a bit faster. The code for finding and inserting nodes is included with the project in treesearch.C. The header file for the TreeNode class, tree.h, can be found in the course include directory. It might be useful to compare the code with the execution of the algorithm, to get a feel for how to make things work.

3. As tree reads its commands from stdin, instead of typing in commands, you can redirect stdin to a file. This is useful for reproducing errors when debugging your program.

4. The code distributed with this project is essentially that of tree, except that the code for removing nodes has been removed. Make it and run it once before adding any code, to make sure every thing's working all right.