Purpose

This lab gives you experience implementing a right and left rotation on a binary tree.

Assignment Prep.

Complete and test the code for your iteratorLevelOrder method from the previous assignment.

Study the right and left rotation algorithms given in L&C and in the lecture notes, so that you understand the design of the methods that you will need to implement in this assignment.

Prior to the assignment, do the following to get started:

Download, save, and unzip the file bintree_rotation.zip on your removable media (floppy disk, Zip disk, or memory stick).

Assignment Activities

The Rotation class has the main method. Its main method sets up two test case binary trees using the LinkedBinaryTree class and calls the LinkedBinaryTree class methods rotateRight and rotateLeft (that you will write below) to rotate the root of each test case tree. It uses the Iterator object returned by the iteratorLevelOrder method to print the contents of each tree both before and after its rotation.

You need to design and add code for two new methods of the LinkedBinaryTree class where indicated.

1. In rotateRight, write code to implement the right rotation algorithm in the L&C text on page 411.

2. In rotateLeft, write code to implement the left rotation algorithm in the L&C text on page 412.

A sample run of the finished program for the right rotation is shown here:

> java Rotation
Contents of rightTree before right rotation
13
7
15
5
10
null
null
3
null
null
null
null
null
Contents of rightTree after right rotation
7
5
13
3
null
10
15
null
null
null
null
null
null
. . .

Report (memo.txt)

In your report, explain when you would want to use the rotateRight or rotateLeft methods and how your code could determine that it needed to do one of these two rotations.