CSCI 200 - Foundational Programming Concepts & Design - Fall 2022

AXC - Forest Walk: Traversing BSTs

→This assignment is due by Thursday, December 08, 2022, 11:59 PM.←
→ As with all assignments, this must be an individual effort and cannot be pair programmed. Any debugging assistance must follow the course collaboration policy and be cited in the comment header block for the assignment.←
→ Do not forget to complete the following labs with this set: LXC

· Instructions · Rubric ·Submission ·

For this assignment, we will verify our tree is created correctly by printing out the tree in different ways and some additional stats.


Tree Traversal


We'll expand our Tree class by adding the following public methods:

To test your implementation, perform in main.cpp the following steps in order:

  1. Create a BinarySearchTree of integers
  2. Add the value 6
  3. Add the value 5
  4. Add the value 7
  5. Add the value 1
  6. Add the value 2
  7. Add the value 9
  8. Add the value 3
  9. printInOrder()
  10. printPreOrder()
  11. printPostOrder()

Your program should display:

In Order:   1 2 3 5 6 7 9
Pre Order:  6 5 1 2 3 7 9
Post Order: 3 2 1 5 9 7 6

Create a second tree with the following steps:

  1. Create a BinarySearchTree of integers
  2. Add the value 5
  3. Add the value 1
  4. Add the value 9
  5. Add the value 7
  6. Add the value 6
  7. Add the value 3
  8. Add the value 2
  9. printInOrder()
  10. printPreOrder()
  11. printPostOrder()

Your program should display:

In Order:   1 2 3 5 6 7 9
Pre Order:  5 1 3 2 9 7 6
Post Order: 2 3 1 6 7 9 5

We'll now add two more ways to traverse the tree:

Your first tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     6 5 1 2 3 7 9
Post Order:    3 2 1 5 9 7 6
Breadth Order: 6 5 7 1 9 2 3
Depth Order:   6 5 1 2 3 7 9

Your second tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     5 1 3 2 9 7 6
Post Order:    2 3 1 6 7 9 5
Breadth Order: 5 1 9 3 7 2 6
Depth Order:   5 1 3 2 9 7 6

We'll now add a way to pretty print by level:

Your first tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     6 5 1 2 3 7 9
Post Order:    3 2 1 5 9 7 6
Breadth Order: 6 5 7 1 9 2 3
Depth Order:   6 5 1 2 3 7 9
By Levels:
Level 1: 6
Level 2: 5 7
Level 3: 1 9
Level 4: 2
Level 5: 3

Your second tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     5 1 3 2 9 7 6
Post Order:    2 3 1 6 7 9 5
Breadth Order: 5 1 9 3 7 2 6
Depth Order:   5 1 3 2 9 7 6
By Levels:
Level 1: 5
Level 2: 1 9
Level 3: 3 7
Level 4: 2 6

Finally, add a method to print the height, or number of levels, of the tree.

Your first tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     6 5 1 2 3 7 9
Post Order:    3 2 1 5 9 7 6
Breadth Order: 6 5 7 1 9 2 3
Depth Order:   6 5 1 2 3 7 9
By Levels:
Level 1: 6
Level 2: 5 7
Level 3: 1 9
Level 4: 2
Level 5: 3
Height: 5

Your second tree should display:

In Order:      1 2 3 5 6 7 9
Pre Order:     5 1 3 2 9 7 6
Post Order:    2 3 1 6 7 9 5
Breadth Order: 5 1 9 3 7 2 6
Depth Order:   5 1 3 2 9 7 6
By Levels:
Level 1: 5
Level 2: 1 9
Level 3: 3 7
Level 4: 2 6
Height: 4

For a final test, create a third tree as follows:

  1. Create a BinarySearchTree of integers
  2. Add the value 5
  3. Add the value 2
  4. Add the value 1
  5. Add the value 7
  6. Add the value 9
  7. Add the value 6
  8. Add the value 3

This tree will print:

In Order:      1 2 3 5 6 7 9
Pre Order:     5 2 1 3 7 6 9
Post Order:    1 3 2 6 9 7 5
Breadth Order: 5 2 7 1 3 6 9
Depth Order:   5 2 1 3 7 6 9
By Levels:
Level 1: 5
Level 2: 2 7
Level 3: 1 3 6 9
Height: 3

Best Practices To Follow



Grading Rubric


Your submission will be graded according to the following rubric.

PointsRequirement Description
5 All labs completed and submitted
LXC
10 Tree functions work correctly
5 Best practices are followed:
  • +5 Code is easily readable, follows best practices, well structured
  • +4 Code is easy to follow, only a few small violations of best practices
  • +3 No egregiously bad practices
  • +2 Lots of violations of best practices
  • +1 Little effort to follow best practices
  • +0 No effort to follow best practices
20 Total Points

→This assignment is due by Thursday, December 08, 2022, 11:59 PM.←
→ As with all assignments, this must be an individual effort and cannot be pair programmed. Any debugging assistance must follow the course collaboration policy and be cited in the comment header block for the assignment.←
→ Do not forget to complete the following labs with this set: LXC


Submission


Always, always, ALWAYS update the header comments at the top of your main.cpp file. And if you ever get stuck, remember that there is LOTS of help available.

It is critical that you follow these steps when submitting homework.

If you do not follow these instructions, your assignment will receive a major deduction. Why all the fuss? Because we have several hundred of these assignments to grade, and we use computer tools to automate as much of the process as possible. If you deviate from these instructions, our grading tools will not work.


Submission Instructions



Here are step-by-step instructions for submitting your homework properly:

  1. Make sure you have the appropriate comment header block at the top of every source code file for this set. The header block should include the following information at a minimum.
    /* CSCI 200: Assignment XC: AXC - Forest Walk: Traversing BSTs
     *  * Author: XXXX (INSERT_NAME) * Resources used (Office Hours, Tutoring, Other Students, etc & in what capacity):  * // list here any outside assistance you used/received while following the * // CS@Mines Collaboration Policy and the Mines Academic Code of Honor *  * XXXXXXXX (MORE_COMPLETE_DESCRIPTION_HERE)  */
    Be sure to fill in the appropriate information, including:
    • Assignment number
    • Assignment title
    • Your name
    • If you received any type of assistance (office hours - whose, tutoring - when), then list where/what/who gave you the assistance and describe the assistance received
    • A description of the assignment task and what the code in this file accomplishes.

    Additionally, update the Makefile for AXC to generate a target executable named AXC.

  2. File and folder names are extremely important in this process. Please double-check carefully, to ensure things are named correctly.
    1. The top-level folder of your project must be named SetXC
    2. Inside SetXC, create 2 sub-folders that are required for this Set. The name of each sub-folder is defined in that Set (e.g. LXC, and AXC).
    3. Copy your files into the subdirectories ofSetXC (steps 2-3), zip this SetXC folder (steps 4-5), and then submit the zipped file (steps 6-11) to Canvas.
    4. For example, when you zip/submit SetXC, there will be 2 sub-folders called LXC, and AXC inside the SetXC folder, and each of these sub-folders will have the associated files.

  3. Using Windows Explorer (not to be confused with Internet Explorer), find the files named BinarySearchTree.hpp, TreeNode.hpp, main.cpp, Makefile.

    STOP: Are you really sure you are viewing the correct assignment's folder?

  4. Now, for AXC, right click on BinarySearchTree.hpp, TreeNode.hpp, main.cpp, Makefile to copy the files. Then, return to the SetXC/AXC folder and right click to paste the files. In other words, put a copy of your homework's BinarySearchTree.hpp, TreeNode.hpp, main.cpp, Makefile source code into the SetXC/AXC folder.

    Follow the same steps for each lab to put a copy of each lab's deliverable into the SetXC/LXC folders. Do this process for SetXC/LXCA (BinarySearchTree.hpp, TreeNode.hpp, main.cpp, Makefile).

    STOP: Are you sure your SetXC folder now has all your code to submit?

    The structure of the submission is as follows:
    • SetXC/
      • AXC/
        • BinarySearchTree.hpp
        • TreeNode.hpp
        • main.cpp
        • Makefile
      • LXCA/
        • BinarySearchTree.hpp
        • TreeNode.hpp
        • main.cpp
        • Makefile

  5. Now, right-click on the "SetXC" folder.
    1. In the pop-up menu that opens, move the mouse "Send to..." and expand the sub-menu.
    2. In the sub-menu that opens, select "Compressed (zipped) folder".

    STOP: Are you really sure you are zipping a SetXC folder with sub-folders that each contain a main.cpp file in it?

  6. After the previous step, you should now see a "SetXC.zip" file.

  7. Now visit the Canvas page for this course and click the "Assignments" button in the sidebar.

  8. Find SetXC, click on it, find the "Submit Assignment" area, and then click the "Choose File" button.

  9. Find the "SetXC.zip" file created earlier and click the "Open" button.

    STOP: Are you really sure you are selecting the right homework assignment? Are you double-sure?

  10. WAIT! There's one more super-important step. Click on the blue "Submit Assignment" button to submit your homework.

  11. No, really, make sure you click the "Submit Assignment" button to actually submit your homework. Clicking the "Choose File" button in the previous step kind of makes it feel like you're done, but you must click the Submit button as well! And you must allow the file time to upload before you turn off your computer!

  12. Canvas should say "Submitted!". Click "Submission Details" and you can download the zip file you just submitted. In other words, verify you submitted what you think you submitted!

In summary, you must zip the "SetXC" folder and only the "SetXC" folder, this zip folder must have several sub-folders, you must name all these folders correctly, you must submit the correct zip file for this homework, and you must click the "Submit Assignment" button. Not doing these steps is like bringing your homework to class but forgetting to hand it in. No concessions will be made for incorrectly submitted work. If you incorrectly submit your homework, we will not be able to give you full credit. And that makes us unhappy.


→This assignment is due by Thursday, December 08, 2022, 11:59 PM.←
→ As with all assignments, this must be an individual effort and cannot be pair programmed. Any debugging assistance must follow the course collaboration policy and be cited in the comment header block for the assignment.←
→ Do not forget to complete the following labs with this set: LXCA