CSCI 2270 - Fall 1996                                     Second Exam - Part 2

First Name___________________________________________

LOGIN Name___________________________________________

THERE ARE SEVEN QUESTIONS. THE FIRST ONE IS WORTH THREE POINTS, AND THE OTHERS
ARE WORTH 12 POINTS EACH.

1. Write a declaration of a struct that could be used to store the data from a
   node in a tree, where each node has integer data and each node can have zero
   to 1000 children. Write the complete declaration in an exact form that will
   compile correctly. Do not omit any part of the declaration.














2. Here is a complete binary tree. How would the values of these nodes be
   stored in an array, using the usual technique for storing a complete
   binary tree in an array? Draw your array below the tree.
                               _______
                              |   8   |
                              |_______|
                        ______/        \__________
                _______/                          \_______
               |   4   |                          |  10   |
               |_______|                          |_______|
               /       \                          / 
      _______ /         \_______          _______/
     |   2   |          |   6   |        |   9   |
     |_______|          |_______|        |_______|

              
           
                  















3.  Here is a binary tree. 
                               _______
                              |   8   |
                              |_______|
                        ______/        \__________
                _______/                          \_______
               |   4   |                          |  10   |
               |_______|                          |_______|
               /       \                          / 
      _______ /         \_______          _______/
     |   2   |          |   6   |        |   9   |
     |_______|          |_______|        |_______|

A. In what order would the nodes of this tree be processed for an
   in-order traversal?


B. In what order would the nodes of this tree be processed for a
   pre-order traversal?


C. In what order would the nodes of this tree be processed for a
   post-order traversal?

   




4. Suppose that we are using               class BinaryTreeNode
   the BinaryTreeNode definition           {
   to the right. Complete the                  int data;
   body of this function. Check the            BinaryTreeNode* left;
   precondition as much as possible.           BinaryTreeNode* right;
                                           };

   void subswap(BinaryTreeNode* node_ptr)
   // Precondition: node_ptr is a non-NULL pointer to a node in a binary tree.
   // Postcondition: The left subtree has been moved and is now the right
   // subtree. The right subtree has been moved and is now the left subtree.
   {




















5. Suppose that we are using                   class BinaryTreeNode
   the BinaryTreeNode definition               {
   to the right. Complete the                      int data;
   body of this function. Notice that              BinaryTreeNode* left;
   the root_ptr could be the NULL                  BinaryTreeNode* right;
   pointer (indicating an empty tree).         };

   int add_data(BinaryTreeNode* root_ptr)
  // Precondition: root_ptr is a root pointer for a binary tree of integers.
  // It could be NULL (indicating an empty tree).
  // Postcondition: The return value is the sum of all the data in all the
  // nodes of the tree.
  {















































6. Suppose that we are using                   class BinaryTreeNode
   the BinaryTreeNode definition               {
   to the right for a binary search                int data;
   tree of integers. Complete the                  BinaryTreeNode* left;
   following code to count how many                BinaryTreeNode* right;
   times the number 42 appears in the          };
   tree. At the end of the code, your
   answer is printed to cout.


   // Assume that root_ptr is the root point of the binary search tree.
   
   size_t answer;
   answer = 0;

   // Now write code that will set answer equal to the number of occurrences
   // of 42 in the tree. This should NOT be a complete function definition--
   // just a few lines of code.







































    cout "There were this many 42's in the tree: " << answer << endl;
   

7. Suppose that we are using                   class BinaryTreeNode
   the BinaryTreeNode definition               {
   to the right for a binary search                int data;
   tree of integers. Complete the                  BinaryTreeNode* left;
   following code to count add another             BinaryTreeNode* right;
   copy of 42 to the tree. Do NOT use          };
   any functions from the toolkit. Just
   write everything from scratch.


   // Assume that root_ptr is the root pointer of the binary search tree.
   // Now write code that will add another copy of 42 to the tree. This
   // should NOT be a complete function definition--just a few lines of
   // code. You may declare local variables if you need to.







































    // At this point, the tree has one more 42.