CSCI 132 Data Structures--Spring 2014

    Assignment 9

    Due at the beginning of class, Friday, May 2, 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    Part 1. Programming a Tree function


    In this problem, you will implement some of the functions for the Binary_tree class discussed in lecture. Specifically, you will write a function that calls a recursive function to count all the nodes of a linked binary tree, and you will write a function to clear a binary tree.

    To start this assignment, copy the files for this assignment which can be found in:

      ~csci132/assignments/assign9

    This folder contains all the files necessary for this assignment. The specification for the Binary_tree class is in the file, binary_tree.h. The implementation is in the file, binary_tree.cc. The file test_tree.cc contains source code for testing the Binary_tree implementation.

    To complete this problem you should do the following:

    • Implement the function, size(). This function should return the result of calling the function, recursive_size() with the appropriately initialized parameters.
    • Implement the function, recursive_size(). This function recursively finds the number of nodes in the tree (or subtree) to which the parameter sub_root points.
    • Implement the function, clear(). This function should return the result of calling the function, recursive_clear() with the appropriately initialized parameters.
    • Implement the function, recursive_clear(). This function recursively clears the tree.

    Hints: recursive_size() takes one parameter, sub_root, which is a pointer to the root (or subroot) of the tree (or subtree) for which the number of nodes will be returned. If sub_root is NULL, the tree is empty, so there are no nodes in the tree. If sub_root is pointing to a node, the number of nodes in the tree is 1 (the node being pointed to) plus the number of nodes in the left sub_tree of that node plus the number of nodes in the right sub_tree of that node.

    recursive_clear() also takes one parameter, sub_root, which is a pointer to the root (or subroot) of the tree (or subtree) to be cleared. If the pointer is NULL, the tree is empty, so it is already cleared. If the pointer points to a node, the function must first clear the lefthand subtree of that node, then clear the righthand subtree of that node. Finally, it must clear the node pointed to by sub_root. This is accomplished by creating a temporary pointer that points to that node, then assigning sub_root to NULL, and finally deleting the node (by deleting the temporary pointer).

    Test your function by compiling and running it with the test_tree.cc code. Use the compile command:

      g++ -g -Wall test_tree.cc -o test_tree

    A sample output is as follows: 

      Creating first test tree.
The tree in preorder is: 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
The tree in inorder is: 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
The tree in postorder is: 
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
The size of the tree is 20
After clearing, the size of the tree is 0

Creating second test tree.
The tree in preorder is: 
5 2 1 3 4 7 6 8 9 10 
The tree in inorder is: 
1 2 3 4 5 6 7 8 9 10 
The tree in postorder is: 
1 4 3 2 6 10 9 8 7 5 
The size of the tree is 10
After clearing, the size of the tree is 0

    When you are done, submit a soft copy of your programs using the submit function. Also copy and paste the 4 functions you wrote for this problem ( size(), recursive_size(), clear() and recursive_clear()), along with your file prologue for binary_tree.cc into a separate file so you can print it out and hand it in.

    Part 2. Working with Binary Trees

    For each of the following problems, write your answer on the Homework 9 Answer sheet.

    1. Determine the order in which the vertices of the following binary tree will be visited under (1) preorder, (2) inorder, and (3) postorder traversal.

    2. Draw expression trees for each of the following expressions, and show the order of visiting the vertices in (1) preorder, (2) inorder, and (3) postorder:

    (a) log n!

    (b) (a - b) - c

    Problem 3 is based on the following binary search tree:

    3. Insert each of the following keys into the preceding binary search tree. Draw the resulting Tree. Show the comparisons of keys that will be made in each case. Do each part independently, inserting the key into the original tree.

    a) m

    b) f

    4. Draw the binary search trees that function insert() will construct for the list of 14 names presented in the following order and inserted into a previously empty binary search tree.

      Jan Guy Jon Ann Jim Eva Amy Tim Ron Kim Tom Roy Kay Dot

    What to turn in:

    • Turn in a hard copy of the prologue and the four functions you implemented from the file:

        binary_tree.cc

      You should copy and paste these into a separate file for printing purposes so that you only print the four functions, clear(), recursive_clear(), size() and recursive_size().

      Make sure you include a file prologue with your name, class, lecture section, the date, and the assignment number, along with a description of the file contents and their purpose. Also include appropriate comments for each of the functions you implement (with proper pre and post conditions).

    • Submit the soft copy of your program using the command:
      ~csci132/bin/submit csci132 assign9
    • Turn in the homework 9 answer sheet with your answers to the problems in part 2 of this assignment.
    • Turn in a discussion log.

    Home | | Syllabus | | Assignments | | Lecture Notes


    Computer Science 132--Data Structures
    Last Modified: April 24, 2015
    Page Expires: January 14, 2015