Assignment #4

Due November 6.

1) 4.8, 4.9, and 4.19 (6 pts.)

2) 4.18, 4.21, and 4.26 (12 pts.)

3) 4.31 (9 pts.)

4) The Great Tree to List Recursion Problem (15 pts. -- submit electronically as well as hard copy)

Write a recursive method 

	public static BinaryNode<AnyType> treeToList(BinaryNode<AnyType> root)
that takes a reference to a binary search tree as a parameter and rearranges the internal pointers of that tree to make it into a circular doubly linked list. The method will return a reference to the circular doubly linked list. The data in each node will remain constant -- only the pointers change, the "left" and "right" pointers of the binary search tree becoming, in effect, the previous and next pointers of a circular doubly linked list. The resulting list must be arranged so that nodes are in increasing order.

Basically you will convert a binary search tree structure that looks like this:

into a sorted circular doubly linked list. The circular doubly linked list should not have a head node, but should be referred to by a pointer to its least element. No new nodes need to be created and no data needs to be moved. Only pointers need to be changed. The resulting circular doubly linked list should look like this:

Use the BinarySearchTree class provided by Weiss (Figure 4.17) to make the tree and to insert elements. BinaryNode<AnyType> (Figure 4.16) will be used for individual nodes. Your conversion method need not create any nodes or move any data -- it only needs to change pointers -- and you should not worry about preserving the original tree. When your method is finished, it should return a circular doubly linked list comprised of BinaryNodes. The steps in public static void main(String[] args) might be as follows:

  1. Make a new BinarySearchTree.
  2. Use insert to fill the tree with Integers.
  3. Print out the tree using the methods in Figure 4.56 in the text.
  4. Call your recursive treeToList method.
  5. Print out the circular doubly linked list using the following method: 
    	public static void printList(BinaryNode<AnyType> list) {
		BinaryNode<AnyType> current = list;
		while (current != null) {
			System.out.print(Integer.toString(current.element) + " ");
			current = current.right;
			if (current == list) break;
		}
		System.out.println();
	}

The conversion can be done in O(n) time -- essentially operating once on each node.

Hints: Trust your recursion! Your recursion should go down the tree, recursively changing the left and right sub-trees into lists, and then appending those lists together with the parent node to make larger lists.

Separate out a utility function 

	public static BinaryNode<AnyType> append(BinaryNode<AnyType> a, BinaryNode<AnyType> b)
that takes two circular doubly linked lists and appends them together to make one list which is returned. Having this separate utility function removes some of the complexity from the recursive function.

Note: The above description uses HTML codes for angle brackets -- so beware of copying and pasting.

EXTRA CREDIT: 4.14 and 4.15. (12 pts.)