Compsci 100e, Spring 2011, Classwork 12

This classwork focuses on implementing trees. Start by snarfing the code under classwork-rodger/12ClwkTrees.

Turn this classwork by submitting it to Clwk12Trees

Part 1 - Trees

The first code we will look at is TreeStuff.java which involves trees.

Here is a Node for a Tree

1. Write the method insert to insert a value into a binary search tree.

2. Write the method printInOrder to print the values in a binary search tree, in order, all on the same line. This method should be recursive.

3. Write the method printSideways to print the tree sideways, indent each node that is further down in the tree. That is, print each node in reverse order, each value on a separate line. If a node is at depth N then print N blanks before printing it. This method should be recursive.

Part 2 - TreeTolist

Thanks to Nick Parlante for this problem.

In a binary search tree, each node contains a single data element and "small" and "large" pointers to sub-trees (i.e. left and right). A binary tree with the values 1 through 5 may be defined as follows:

Now, consider the data as a circular doubly linked list.

The challenge is to take an ordered binary tree and rearrange the internal pointers to make a circular doubly linked list out of it. The left pointer should play the role of prev and the right pointer should play the role of next. The list should be arranged so that the nodes are in increasing order.

1. Write the method join that given two TreeNodes (that are really now two nodes in a linked list), joins them together so that the second immediately follow the first. Sets the .next of the first and the .prev of the second.

2. Write the method append that assumes each TreeNode has been converted into a circular doubly linked list and it appends them (a followed by b) and returns the new circular doubly linked list.

3. Write a recursive method treeToList(TreeNode root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The left pointers work like the prev field in a doubly linked list and the right pointers work similar to the next field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time -- essentially operating on each node once.

4. Complete the printCircularList method to print out the nodes in a circular linked list. That is, print out the info field for each node.

Submit

Turn this classwork by submitting it to Clwk12Trees