Note: no late submission will be accepted, as we will go over the answers in class.
[Binary Tree, 15pts] Read through the binaryTreeType class de ned on pages 609-616 and 628-632. Add a recursive function, leafCount(), that returns the num-ber of leaf nodes in a binary tree. Convert this function to a non-recursive version nr-leafCount(). Turn in your source code printout for these two functions.
[AVL tree, 5pts] Use a diagram to explain when a right-left double rotation (right rotation followed by a left rotation) is needed in AVL insertion, and how it’s conducted.
[AVL tree, 5pts] Exercise 19, page 680.
[AVL tree, 5pts] Exercise 20, page 681.
[Heap, 5pts] The following elements are inserted into an empty Max-Heap in the fol-lowing order:
2, 3, 1, 4, 6, 12, 15, 22, 11, 5
Draw the resulting heap (use the logical (tree) representation).
[Build Heap, 10pts] Exercise 12, page 595.
[Heapsort, 10pts] Exercise 13, page 595.
[Heap, 5pts] Draw all legal Max-Heaps containing the 4 elements 1, 2, 3, 4.
[Heap, 5pts] Draw all legal Max-Heaps containing the 5 elements 1, 2, 3, 4, 5.
[Recursion 5pts] An implementation of the n-queens puzzle is attached under Project 3 assignment. Compile and test it for n = 1; 2; 3; :::10. Turn in the number of solutions for each n (e.g., the number of solutions for n = 8 is 92).
[Recursion, 10pts] Exercise 13, page 389. (Note: by \algorithm", you only need to write your solution into an expression like Equation 6-3 on page 366.)
[Recursion, 10pts] Exercise 14, page 390.
[Recursion, 10pts] The sequential search algorithm given in Chapter 3 (seqSearch() on page 181) is nonrecursive. Write and implement a recursive version of the sequential search algorithm. Turn in your source code printout.
