1. Draw the data structures resulting from the following sequences of operations (show only the final data structure, not all of the intermediate steps).

    (a) Be sure to label which end is the top and which is the bottom 

       S = NewStack();
   Push(S,5);
   Push(S,Top(S)+3);
   Push(S,6);
   Pop(S);
   Push(S,9);
   Push(S,Pop(S)-2);
   Push(S,0);

    (b) Be sure to indicate which end is the front and which is the back 

       Q = NewQueue();
   Enqueue(Q,5);
   Enqueue(Q,0);
   Enqueue(Q,1);
   Dequeue(Q);
   Enqueue(Q,3);
   Enqueue(Q,Front(Q)+5);
   Enqueue(Q,Dequeue(Q));
   Enqueue(Q,Front(Q));
   Enqueue(Q,Dequeue(Q)+1);
   Enqueue(Q,5);

    (c) Use lazy deletion 

       T = New Tree();
   Insert(T,5);
   Insert(T,9);
   Insert(T,7);
   Delete(T,5);
   Insert(T,11);
   Insert(T,3);
   Insert(T,4);
   Insert(T,1);
   Delete(T,3);

    (d) Repeat (c), but delete by replacing the value with its largest left descendent

     

  2. Exercise 4.39

     

  3. Write a function that traverses an integer Binary Search Tree and calculates its average value (where average is defined to be the sum of all the node values divided by the total number of nodes). You should write this operating on the data structure directly, not using tree operations:

                   C                                      C++
   --------------------------              -------------------------
   typedef struct _TreeNode {              /* TreeNode defined as in C */
     int data;               
     struct _TreeNode *Left;               class List {
     struct _TreeNode *Right;                private:
   } TreeNode;                                 TreeNode *root; 
                                               ...
   typedef TreeNode *Tree;                 }

     

  4. Show the result of inserting 20 into the following AVL tree: 
    
               10
              /  \
             5    13
            /    /  \
           1   11    15
            \          \
             3          17