CPSC 241-002 Computer Science IV
(Data Structures and Algorithms)
Fall 1998
TTh 12:30--1:45 Daniel 408
Assignment 6
<http://andrewd.ces.clemson.edu/courses/cpsc241/fall98/hw/asg6.html>

Objectives:
To implement the binary (search) tree data structure and its associated member functions.

Due date:
10/15/98

Description:
  1. Create a Tree class to represent a binary tree data structure. An example Tree node is represented by the diagram below.

    The Tree node is similar in structure to a doubly-linked list node, however, the use of the tree structure differs significantly.

    You may use either inheritance or composition to represent the tree data structure. For example, you may follow the example of either doubly-linked implementation used previously, i.e., in one a head node subclass was derived from the queue node class, in the other, only a queue node was required. Whichever strategy you choose, keep in mind that although every node in the tree should contain a key data value, only one node can act as the proper root node.

    Provide the following member functions for the Tree class:
    data() returns the private key data member (not really needed)
    insert() inserts a node into the tree
    remove() removes a node from the tree
    preorder() preorder tree traversal printing contents (the key) of each node
    inorder() inorder tree traversal printing contents (the key) of each node
    postorder() postorder tree traversal printing contents (the key) of each node

    Your code should be arranged so that the Tree class interface is in separate header (.h) file, while the class interface is in a .c file.

  2. Write a program to exercise the Tree class by creating a user-specified sized tree of integers. Use the random number generator to fill in the data (make sure you remember to seed the random number generator first!). This is similar to previous programs, except that now you're using the Tree class to automatically create a sorted (in terms of inorder traversal) tree representation of the data.

    Use inorder traversal to verify proper data organization (the output should be sorted).

    Make sure you test the remove() member function thoroughly. That is, don't remove all the nodes until the tree is empty, rather, remove user-selected nodes and re-print the tree contents. Do this repeatedly to make sure your remove() routine handles every case of node removal (especially the case when both of the node's subtrees are non-empty).

    Here's the sample output (notice, and verify that the root node is being removed): 

    Enter tree size: 7
inserting [0]: 10030
inserting [1]: 15648
inserting [2]: 7661
inserting [3]: 21828
inserting [4]: 189
inserting [5]: 13187
inserting [6]: 2811
printing inorder:
189
2811
7661
10030
13187
15648
21828

Enter node to be removed: 10030
removed node: 10030
printing inorder:
189
2811
7661
13187
15648
21828
    Your code should be arranged so that the main() routine is in a separate .c file. Use a Makefile to compile all the modules.

    Warning: while the main() portion of this assignment may seem somewhat rudimentary, the tree conceptualization and proper implementation may not be. In particular, the remove() routine is the most difficult to implement properly. Start early!

    Suggestions:
    1. Keep a pointer to the root node somewhere. This pointer should be NULL if the tree is empty, otherwise, it should point to the root Tree node.

    2. For the remove() routine, a useful Tree member function is predecessor(). This routine should find a given node's inorder ``immediate predecessor''. A good way to implement this is for the predecessor() routine to expect a pointer to the given node's left child (see below). The predecessor() routine would then search down the given node's left child's right subtree (re-read this carefully).

      The predecessor() routine should return a pointer to the given node's immediate predecessor. It should also set a pointer to the predecessor's parent node (through pass-by-reference).

      Putting together all the above suggestions, an example call of the routine (from remove()) might be: 

      pred_parent = tree_node;
pred = predecessor(tree_node->lp,pred_parent);
    3. It is important to keep track of nodes' parent nodes in the remove() routine. Special cases, however, arise and need to be handled correctly. One particular such case is when the parent node points to the node that needs to be removed (or is NULL, depending on your implementation). That is, the node that needs to be removed has no parent, or in other words, it is the root. Another similar special circumstance arises when the predecessor() routine simply returns the given node and does not alter pred_parent (when might this happen?). In this case, the given node's (the one that is to be deleted) left child is its immediate predecessor. Therefore, the predecessor's parent pointer would also point to the node to be deleted.

    What to hand in:
    ``Professional-quality'' writeup, including:
    1. Cover page containing:
      Course Id--Section No.
      Name:
      SS No:
      Assignment No.
    2. Assignment description
    3. Solution description (e.g., program design, description of algorithm, etc., however appropriate).
    4. Lessons learned, identified interesting features of your program
    5. Appendix A: Source code listing
    6. Appendix B: Sample input (if any)
    7. Appendix C: Sample output
    The entire document should be a clearly written account of what you were to accomplish, what you in fact did accomplish, and what you learned (how you accomplished it). The code and sample runs, listed in the appendices, should be clearly documented (e.g., document the source code, generate informative output).

    The general presentation of your document counts! (This includes qualities such as neatness, formatting, and legibility.)